On the public citation graph
Recognizing $P_4 $-Sparse Graphs in Linear Time
0 signed · 71 inferred · view as graph
Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.
Is this your work? Sign in with ORCID and put your name on the
claims that are yours.
Reference health. See whether every reference in this work resolves to a
known work and none has been retracted — and get a dated CiteStamped
badge you can embed.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1002/sapm198981179openalex-snapshot
P4‐Reducible Graphs—Class of Uniquely Tree‐Representable Graphs
inferredcites →https://doi.org/10.1007/3-540-52048-1_28openalex-snapshot
A linear-time recognition algorithm for P 4-reducible graphs
inferredcites →https://doi.org/10.1007/978-1-349-03521-2openalex-snapshot
Graph Theory with Applications
inferredcites →https://doi.org/10.1016/0166-218x(81)90013-5openalex-snapshot
Complement reducible graphs
inferredcites →https://doi.org/10.1016/0166-218x(92)90036-aopenalex-snapshot
A tree representation for P4-sparse graphs
inferredcites →https://doi.org/10.1137/0214065openalex-snapshot
A Linear Recognition Algorithm for Cographs
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1007/10692760_1openalex-snapshot
Linear Time Solvable Optimization Problems on Graphs of Bounded Clique Width
inferred← citeshttps://doi.org/10.1007/11533719_82openalex-snapshot
On the Recognition of Probe Graphs of Some Self-Complementary Classes of Perfect Graphs
inferred← citeshttps://doi.org/10.1007/11917496_23openalex-snapshot
A Fully Dynamic Algorithm for the Recognition of P 4-Sparse Graphs
inferred← citeshttps://doi.org/10.1007/3-540-60618-1_63openalex-snapshot
On the isomorphism of graphs with few P4s
inferred← citeshttps://doi.org/10.1007/978-3-030-83823-2_45openalex-snapshot
Building a Larger Class of Graphs for Efficient Reconfiguration of Vertex Colouring
inferred← citeshttps://doi.org/10.1007/978-3-319-09174-7_2openalex-snapshot
Study of Identifying Code Polyhedra for Some Families of Split Graphs
inferred← citeshttps://doi.org/10.1007/978-3-540-24838-5_7openalex-snapshot
Simple Max-Cut for Split-Indifference Graphs and Graphs with Few P 4’s
inferred← citeshttps://doi.org/10.1007/978-3-540-39890-5_31openalex-snapshot
Recognizing Bipolarizable and P 4-Simplicial Graphs
inferred← citeshttps://doi.org/10.1007/978-3-540-70918-3_30openalex-snapshot
An Optimal, Edges-Only Fully Dynamic Algorithm for Distance-Hereditary Graphs
inferred← citeshttps://doi.org/10.1007/978-3-642-17461-2_27openalex-snapshot
A Novel Branching Strategy for Parameterized Graph Modification Problems
inferred← citeshttps://doi.org/10.1007/978-3-642-22685-4_10openalex-snapshot
Cograph Editing: Complexity and Parameterized Algorithms
inferred← citeshttps://doi.org/10.1007/978-3-642-32147-4_28openalex-snapshot
The Packing Coloring Problem for (q,q-4) Graphs
inferred← citeshttps://doi.org/10.1007/s00285-020-01469-yopenalex-snapshot
Best match graphs and reconciliation of gene trees with species trees
inferred← citeshttps://doi.org/10.1007/s00373-008-0829-1openalex-snapshot
On the b-Coloring of Cographs and P 4-Sparse Graphs
inferred← citeshttps://doi.org/10.1007/s00373-012-1269-5openalex-snapshot
On the Minimum Sum Coloring of P 4-Sparse Graphs
inferred← citeshttps://doi.org/10.1007/s00373-020-02230-4openalex-snapshot
Spiders and their Kin: An Investigation of Stanley’s Chromatic Symmetric Function for Spiders and Related Graphs
inferred← citeshttps://doi.org/10.1007/s11786-015-0233-1openalex-snapshot
Spiders can be Recognized by Counting Their Legs
inferred← citeshttps://doi.org/10.1016/0012-365x(93)90539-6openalex-snapshot
A decomposition for a class of (P5,P5)-free graphs
inferred← citeshttps://doi.org/10.1016/0166-218x(94)00012-3openalex-snapshot
Linear time optimization algorithms for P4-sparse graphs
inferred← citeshttps://doi.org/10.1016/j.cosrev.2010.01.001openalex-snapshot
A survey of the algorithmic aspects of modular decomposition
inferred← citeshttps://doi.org/10.1016/j.dam.2005.02.004openalex-snapshot
Efficient parallel recognition of cographs
inferred← citeshttps://doi.org/10.1016/j.dam.2005.04.001openalex-snapshot
On the b-dominating coloring of graphs
inferred← citeshttps://doi.org/10.1016/j.dam.2010.10.019openalex-snapshot
Characterization and recognition of P4 -sparse graphs partitionable into k independent sets and ℓ cliques
inferred← citeshttps://doi.org/10.1016/j.dam.2013.01.016openalex-snapshot
The parametric complexity of graph diameter augmentation
inferred← citeshttps://doi.org/10.1016/j.dam.2013.10.014openalex-snapshot
Dot product dimensions of graphs
inferred← citeshttps://doi.org/10.1016/j.dam.2013.10.031openalex-snapshot
Maximization coloring problems on graphs with few P4
inferred← citeshttps://doi.org/10.1016/j.dam.2022.06.042openalex-snapshot
From modular decomposition trees to level-1 networks: Pseudo-cographs, polar-cats and prime polar-cats
inferred← citeshttps://doi.org/10.1016/j.disc.2005.11.089openalex-snapshot
On bipartite graphs with weak density of some subgraphs
inferred← citeshttps://doi.org/10.1016/j.disc.2005.12.008openalex-snapshot
Minimal separators in P4 -sparse graphs
inferred← citeshttps://doi.org/10.1016/j.disc.2008.01.014openalex-snapshot
The Graph Sandwich Problem for P4 -sparse graphs
inferred← citeshttps://doi.org/10.1016/j.disopt.2016.06.002openalex-snapshot
Progress on the description of identifying code polyhedra for some families of split graphs
inferred← citeshttps://doi.org/10.1016/j.ejc.2026.104345openalex-snapshot
Graph classes with few P 4 ’s: Universality and Brownian graphon limits
inferred← citeshttps://doi.org/10.1016/j.endm.2009.11.048openalex-snapshot
Minimum Sum Coloring of P4-sparse graphs
inferred← citeshttps://doi.org/10.1016/j.endm.2010.05.071openalex-snapshot
The k-limited packing and k-tuple domination problems in strongly chordal, P4-tidy and split graphs
inferred← citeshttps://doi.org/10.1016/j.endm.2011.05.062openalex-snapshot
Polynomial instances of the Packing Coloring Problem
inferred← citeshttps://doi.org/10.1016/j.endm.2013.10.034openalex-snapshot
-domination for chordal graphs and related graph classes
inferred← citeshttps://doi.org/10.1016/j.ipl.2003.11.002openalex-snapshot
Efficient robust algorithms for the Maximum Weight Stable Set Problem in chair-free graph classes
inferred← citeshttps://doi.org/10.1016/j.ipl.2011.09.002openalex-snapshot
The multiple domination and limited packing problems in graphs
inferred← citeshttps://doi.org/10.1016/j.ipl.2015.02.007openalex-snapshot
A one-to-one correspondence between potential solutions of the cluster deletion problem and the minimum sum coloring problem, and its application to P4 -sparse graphs
inferred← citeshttps://doi.org/10.1016/j.tcs.2011.11.040openalex-snapshot
Complexity and parameterized algorithms for Cograph Editing
inferred← citeshttps://doi.org/10.1016/j.tcs.2012.03.020openalex-snapshot
A fully dynamic algorithm for the recognition of P4 -sparse graphs
inferred← citeshttps://doi.org/10.1016/j.tcs.2014.11.014openalex-snapshot
Generalized limited packings of some graphs with a limited number of P4 -partners
inferred← citeshttps://doi.org/10.1016/j.tcs.2019.12.033openalex-snapshot
Complexity of modification problems for reciprocal best match graphs
inferred← citeshttps://doi.org/10.1016/s0012-365x(96)00177-xopenalex-snapshot
On semi-P4-sparse graphs
inferred← citeshttps://doi.org/10.1016/s0012-365x(96)00180-xopenalex-snapshot
Scattering number and modular decomposition
inferred← citeshttps://doi.org/10.1016/s0166-218x(01)00220-7openalex-snapshot
Bandwidth and topological bandwidth of graphs with few P4's
inferred← citeshttps://doi.org/10.1016/s0166-218x(03)00180-xopenalex-snapshot
On variations of P4-sparse graphs
inferred← citeshttps://doi.org/10.1016/s0166-218x(97)00085-1openalex-snapshot
A fast parallel algorithm to recognize P4-sparse graphs
inferred← citeshttps://doi.org/10.1016/s0166-218x(97)90120-7openalex-snapshot
On the structure of graphs with few P4s
inferred← citeshttps://doi.org/10.1016/s0166-218x(99)00114-6openalex-snapshot
On the P4-components of graphs
inferred← citeshttps://doi.org/10.1016/s0166-218x(99)00140-7openalex-snapshot
Recognition and isomorphism of tree-like P4-connected graphs
inferred← citeshttps://doi.org/10.1016/s0304-3975(96)00220-4openalex-snapshot
On extended P4-reducible and extended P4-sparse graphs
inferred← citeshttps://doi.org/10.1016/s1571-0653(05)80014-9openalex-snapshot
SIMPLE MAX-CUT for unit interval graphs and graphs with few P4s
inferred← citeshttps://doi.org/10.1137/140978053openalex-snapshot
Pairwise Compatibility Graphs: A Survey
inferred← citeshttps://doi.org/10.1142/s0129054199000083openalex-snapshot
ON GRAPHS WITH LIMITED NUMBER OF P4-PARTNERS
inferred← citeshttps://doi.org/10.1142/s0129054199000241openalex-snapshot
ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P4'S
inferred← citeshttps://doi.org/10.1142/s1793830912500085openalex-snapshot
BOUNDED SEARCH TREE ALGORITHMS FOR PARAMETRIZED COGRAPH DELETION: EFFICIENT BRANCHING RULES BY EXPLOITING STRUCTURES OF SPECIAL GRAPH CLASSES
inferred← citeshttps://doi.org/10.3390/a16060289openalex-snapshot
Adding a Tail in Classes of Perfect Graphs
inferred← citeshttps://doi.org/10.48550/arxiv.0912.1457openalex-snapshot
A survey on algorithmic aspects of modular decomposition
inferred← citeshttps://doi.org/10.48550/arxiv.1411.2105openalex-snapshot
Spiders can be recognized by counting their legs
inferred← citeshttps://doi.org/10.5753/etc.2025.8228openalex-snapshot
Independent locating-dominating sets in P4-sparse graphs
Editorial review for independent work. ICSAC — the Institute for Complexity
Science and Advanced Computing — runs a structured editorial panel for researchers
publishing outside journals, and publishes on CiteStamp rails. Submission is free
and goes through ORCID: icsacinstitute.org/submit.