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 (only showing first 100 items - show all)

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 ⋮ 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

Cites Work

• 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
• 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

This page was built for publication: Claw-free graphs---a survey