Claw-free graphs---a survey

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

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

Publication date: 13 July 1997

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

zbMATH Keywords

survey; invariants; cycles; extremal problems; domination; factors; claw-free graphs; hamiltonicity

Mathematics Subject Classification ID

05-02: Research exposition (monographs, survey articles) pertaining to combinatorics

05C38: Paths and cycles

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

05C45: Eulerian and Hamiltonian graphs

Related Items

Unnamed Item, Eliminating graphs by means of parallel knock-out schemes, 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, Hamiltonian properties of triangular grid graphs, Upper bounds and algorithms for parallel knock-out numbers, Forbidden subgraphs, hamiltonicity and closure in claw-free graphs, \(D_ \lambda\)-cycles in \(\lambda\)-claw-free graphs, Characterizations and algorithmic applications of chordal graph embeddings, On local and global independence numbers of a graph, Cuts leaving components of given minimum order, On Hamiltonicity of \{claw, net\}-free graphs, Mutual exclusion scheduling with interval graphs or related classes. II, Forbidden subgraphs that imply 2-factors, Collapsible biclaw-free graphs, Path extendability of claw-free graphs, Unnamed Item, Computing Sharp 2-Factors in Claw-Free Graphs

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”
• How To Color Claw-Free Perfect Graphs
• 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
• Some sufficient conditions for the existence of a 1-factor
• Hamiltonian cycles in 3‐connected 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
• 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
• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item