Claw-free graphs---a survey

DOI10.1016/S0012-365X(96)00045-3zbMath0879.05043OpenAlexW2092366448WikidataQ55952667 ScholiaQ55952667MaRDI QIDQ1356695

Evelyne Flandrin, Zdeněk Ryjáček, Ralph J. Faudree

Publication date: 13 July 1997

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0012-365x(96)00045-3

zbMATH Keywords

surveyinvariantscyclesextremal problemsdominationfactorsclaw-free graphshamiltonicity

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45)

Related Items

Disjunctive total domination in graphs, Bounds on the leaf number in graphs of girth 4 or 5, Hamiltonian line graphs with local degree conditions, On the performance guarantee of first fit for sum coloring, Finding and counting small induced subgraphs efficiently, Padmakar-Ivan Index of Some Types of Perfect Graphs, On cycle-nice claw-free graphs, Mock threshold graphs, Sharp upper bounds on the minimum number of components of 2-factors in claw-free graphs, On Hamiltonicity of regular graphs with bounded second neighborhoods, Compressed cliques graphs, clique coverings and positive zero forcing, \(D_ \lambda\)-cycles in \(\lambda\)-claw-free graphs, Hamiltonian cycles in linear-convex supergrid graphs, Unnamed Item, More aspects of arbitrarily partitionable graphs, Minimum degree conditions for the Hamiltonicity of 3-connected claw-free graphs, Coloring graph classes with no induced fork via perfect divisibility, Eliminating graphs by means of parallel knock-out schemes, Characterizations and algorithmic applications of chordal graph embeddings, Some local-global phenomena in locally finite graphs, Claw-free strictly Deza graphs, Degree and neighborhood conditions for Hamiltonicity of claw-free graphs, Polynomially determining spanning connectivity of locally connected line graphs, Vertex disjoint copies of \(K_{1 , 4}\) in claw-free graphs, The maximum independent union of cliques problem: complexity and exact approaches, On weights of induced paths and cycles in claw-free andK1,r-free graphs, Generalizations of Dirac's theorem in Hamiltonian graph theory -- a survey, A note on anti-coordination and social interactions, Semipaired domination in claw-free cubic graphs, Unnamed Item, Clique coverings and claw-free graphs, Forbidden induced subgraphs for star-free graphs, Exact algorithms for finding longest cycles in claw-free graphs, The \(k\)-in-a-path problem for claw-free graphs, Clawfreeness of the powers of a graph, Several improved asymptotic normality criteria and their applications to graph polynomials, Improving upper bounds for the distinguishing index, On Hamiltonicity of \{claw, net\}-free graphs, Sufficient Conditions for a Connected Graph to Have a Hamiltonian Path, On local and global independence numbers of a graph, Weights of induced subgraphs in \(K_{1,r}\)-free graphs, Disjoint cliques in claw-free graphs, Hamiltonian properties of locally connected graphs with bounded vertex degree, Locating-total domination in claw-free cubic graphs, Cycle traversability for claw-free graphs and polyhedral maps, Dominating set is fixed parameter tractable in claw-free graphs, On \(s\)-Hamiltonicity of net-free line graphs, A characterization of claw-free \(b\)-perfect graphs, How many conjectures can you stand? A survey, Total domination in claw-free graphs with minimum degree 2, Maximally edge-connected and vertex-connected graphs and digraphs: A survey, Bounds on total domination in claw-free cubic graphs, Positive Zero Forcing and Edge Clique Coverings, Parameterized complexity of induced graph matching on claw-free graphs, A proof of a conjecture on diameter 2-critical graphs whose complements are claw-free, Spanning \(k\)-forests with large components in \(K_{1,k+1}\)-free graphs, Progress on the Murty-Simon conjecture on diameter-2 critical graphs: a survey, Induced cycles in graphs, Domination When the Stars Are Out, Free fermions behind the disguise, Mutual exclusion scheduling with interval graphs or related classes. II, Perfect matchings and \(K_{1,p}\)-restricted graphs, Forbidden subgraphs that imply 2-factors, Total forcing and zero forcing in claw-free cubic graphs, Forbidden pairs with a common graph generating almost the same sets, Path factors and parallel knock-out schemes of almost claw-free graphs, Closure concept for 2-factors in claw-free graphs, Cuts leaving components of given minimum order, On a conjecture on total domination in claw-free cubic graphs, Computing Sharp 2-Factors in Claw-Free Graphs, Collapsible biclaw-free graphs, Path extendability of claw-free graphs, Upper paired-domination in claw-free graphs, Computing sharp 2-factors in claw-free graphs, A clique-covering sufficient condition for hamiltonicity of graphs, Partitioning the vertices of a cubic graph into two total dominating sets, 2-connected Hamiltonian claw-free graphs involving degree sum of adjacent vertices, Deficiency and forbidden subgraphs of connected, locally-connected graphs, Total coloring conjecture for certain classes of graphs, Hamiltonian properties of triangular grid graphs, 2-factors with bounded number of components in claw-free graphs, Hamiltonicity in Partly claw-free graphs, Declawing a graph: polyhedra and branch-and-cut algorithms, Upper bounds and algorithms for parallel knock-out numbers, Minimal claw-free graphs, Zero forcing in claw-free cubic graphs, On the independence number of traceable 2-connected claw-free graphs, The parameterized complexity of the induced matching problem, Domination versus total domination in claw-free cubic graphs, Edge decomposition of connected claw-free cubic graphs, Unnamed Item, Upper total domination in claw-free cubic graphs, Edge-distinguishing of star-free graphs, Forbidden subgraphs, hamiltonicity and closure in claw-free graphs, The feasibility problem for line graphs, Disjoint cycles with partial degree conditions in claw-free graphs, Forbidden subgraphs for longest cycles to contain vertices with large degrees, Equivalence of Jackson's and Thomassen's conjectures, Set graphs. III: Proof pearl: Claw-free graphs mirrored into transitive hereditarily finite sets, Triangles and (total) domination in subcubic graphs, Determining finite connected graphs along the quadratic embedding constants of paths, Conjecture of TxGraffiti: Independence, domination, and matchings, Degree sums of adjacent vertices for traceability of claw-free graphs, Results on the small quasi-kernel conjecture, Linear‐time algorithms for eliminating claws in graphs, Line graphs with a Cohen-Macaulay or Gorenstein clique complex, Radius, leaf number, connected domination number and minimum degree, \(K_{1, 2}\)-isolation number of claw-free cubic graphs, Finding and counting small induced subgraphs efficiently, Semitotal domination in claw-free cubic graphs, Spanning paths and cycles in triangle-free graphs, Hamiltonian cycles and 2-dominating induced cycles in claw-free graphs, Intersection graphs of non-crossing paths, Unnamed Item, The cycle spectrum of claw-free Hamiltonian graphs, When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time, Unnamed Item, Distinguished Minimal Topological Lassos

Cites Work

• Which claw-free graphs are perfectly orderable?
• On Hamiltonian claw-free graphs
• Cycles of given length in some \(K_{1,3}\)-free graphs
• Extending cycles in graphs
• On domination and independent domination numbers of a graph
• Stability in CAN-free graphs
• On the chromatic index of multigraphs without large triangles
• On hamiltonian line graphs and connectivity
• Pancyclism in hamiltonian graphs
• Some localization theorems on Hamiltonian circuits
• The struction of a graph: Application to CN-free graphs
• The chromatic number of graphs which induce neither \(K_{1,3}\) nor \(K_ 5-e\)
• Matching theory
• The monotone circuit complexity of Boolean functions
• A note on the edge-reconstruction of \(K_{1,m}\)-free graphs
• Paw-free graphs
• The strong perfect graph conjecture for pan-free graphs
• Recognizing claw-free perfect graphs
• Applications of edge coloring of multigraphs to vertex coloring of graphs
• On the chromatic number of a graph with two forbidden subgraphs
• A note on locally connected and Hamiltonian-connected graphs
• On maximal independent sets of vertices in claw-free graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Algorithms for minimum covering by cliques and maximum clique in claw- free perfect graphs
• A polynomial algorithm for the minimum weighted clique cover problem on claw-free perfect graphs
• On stable set polyhedra for K//(1,3)free graphs
• Forbidden subgraphs and Hamiltonian properties and graphs
• The edge Hamiltonian path problem is NP-complete
• Existence of dominating cycles and paths
• Hamiltonism, degree sum and neighborhood intersections
• Hamiltonian properties of graphs with large neighborhood unions
• On graphs with equal domination and independent domination numbers
• Hamiltonicity in claw-free graphs
• On independent generalized degrees and independence numbers in \(K(1,m)\)- free graphs
• Stability number of bull- and chair-free graphs
• The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
• Hamilton cycles in regular 2-connected graphs
• A note on \(K_ 4\)-closures in hamiltonian graph theory
• A strengthening of Ben Rebea's lemma
• Extending matchings in claw-free graphs
• Hamiltonicity of bipartite biclaw-free graphs
• Forbidden induced subgraphs for line graphs
• Longest cycles in regular 2-connected claw-free graphs
• Quasi-claw-free graphs
• Hamiltonicity in 2-connected graphs with claws
• A generalization of Fan's condition for Hamiltonicity, pancyclicity, and Hamiltonian connectedness
• On the numbers of independent \(k\)-sets in a claw free graph
• Some applications of Vizing's theorem to vertex colorings of graphs
• Hamiltonicity in claw-free graphs through induced bulls
• Degree conditions and cycle extendability
• Dominating cycles in bipartite biclaw-free graphs
• Sufficient conditions for a graph to be Hamiltonian
• Long paths and cycles in tough graphs
• A note on Hamiltonian circuits
• Tough graphs and Hamiltonian circuits.
• Graph-theoretic parameters concerning domination, independence, and irredundance
• Forbidden subgraphs and hamiitonian properties in the square of a connected graph
• Hamiltonian results inK1,3-free graphs
• Connected, locally 2-connected,K1,3-free graphs are panconnected
• A necessary and sufficient condition for connected, locally k-connected k1,3-free graphs to be k-hamiltonian
• Factors and factorizations of graphs—a survey
• Longest paths and cycles in K1,3-free graphs
• A new sufficient condition for hamiltonian graphs
• The NP-completeness column: an ongoing guide
• Stability, domination and irredundance in a graph
• Hamilton cycles in claw-free graphs
• Claw‐free graphs are edge reconstructible
• 3-Connected line graphs of triangular graphs are panconnected and 1-hamiltonian
• Existence of Δλ-cycles and Δλ-paths
• The square of a connected S(K1,3)-free graph is vertex pancyclic
• On partitioning the edges of graphs into connected subgraphs
• Every connected, locally connected nontrivial graph with no induced claw is hamiltonian
• Note on Choudum's “chromatic bounds for a class of graphs”
• Local properties of graphs
• How To Color Claw-Free Perfect Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A characterization of domination perfect graphs
• Updating the hamiltonian problem—A survey
• Regular factors in K_1,3‐free graphs
• Regular factors in K_1,n free graphs
• 2‐neighborhoods and hamiltonian conditions
• Graphs with 1-Factors
• 1-Factors and Antifactor Sets
• CHROMATIC BOUNDS FOR A CLASS OF GRAPHS
• On the existence of 1-factors in partial squares of graphs
• Some sufficient conditions for the existence of a 1-factor
• Hamiltonian cycles in 3‐connected claw‐free graphs
• Factors of claw-free graphs
• Mengerian properties, hamiltonicity, and claw‐free graphs
• Almost claw‐free graphs
• A note on the characterization of domination perfect graphs
• On the stability number of AH‐free graphs
• Generalized degree conditions for graphs with bounded independence number
• Reflections on graph theory
• Hamiltonicity for K_{1, r}‐free graphs
• Hamiltonian cycles in 2‐connected claw‐free‐graphs
• Cycles through particular subgraphs of claw‐free graphs
• On graphs satisfying a local ore-type condition
• On claw-freeM-oriented critical kernel-imperfect digraphs
• Disjoint cycles in star-free graphs
• Toughness and hamiltonicity in almost claw-free graphs
• Paths, Trees, and Flowers
• On the Cube of a Graph
• Characterizations of derived graphs
• Trees with Hamiltonian square
• The binding number of a graph and its Anderson number
• A Characterization of Comparability Graphs and of Interval Graphs
• Hamiltonian circuits in N₂‐locally connected K_1,3‐free graphs