On the Erdős-Gyárfás conjecture in claw-free graphs

DOI10.7151/DMGT.1732MaRDI QIDQ2509554zbMATH OpenOpenAlexWikidataFDO

Authors Pouria Salehi Nowbandegani, H. Esfandiari, Mohammad Hassan Shirdareh Haghighi, Khodakhast Bibak

Publication date 28 July 2014

Published in Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported

Full work available at URL https://arxiv.org/abs/1109.5398

zbMATH Keywords

cyclesclaw-free graphsErdős-Gyárfás conjecture

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex degrees (05C07) Paths and cycles (05C38)

Abstract: The ErdH{o}s-Gy'{a}rf'{a}s conjecture states that every graph with minimum degree at least three has a cycle whose length is a power of 2. Since this conjecture has proven to be far from reach, Hobbs asked if the ErdH{o}s-Gy'{a}rf'{a}s conjecture holds in claw-free graphs. In this paper, we obtain some results on this question, in particular for cubic claw-free graphs.

Recommendations

• An approximate version of Hadwiger's conjecture for claw-free graphs
• Vizing's conjecture: A two-thirds bound for claw-free graphs
• scientific article; zbMATH DE number 7274067
• Claw-free graphs---a survey
• On pancyclic claw-free graphs
• Publication:4489163
• On a conjecture on total domination in claw-free cubic graphs
• The structure of claw-free graphs
• On Hamiltonian claw-free graphs
• Double-critical graph conjecture for claw-free graphs

Cites work

• scientific article; zbMATH DE number 1735729 (Why is no real title available?)
• scientific article; zbMATH DE number 1943958 (Why is no real title available?)
• scientific article; zbMATH DE number 1472112 (Why is no real title available?)
• scientific article; zbMATH DE number 2170455 (Why is no real title available?)
• Graph theory
• Some old and new problems in various branches of combinatorics
• Unavoidable cycle lengths in graphs

Cited in

(16)

• scientific article; zbMATH DE number 7080199 (Why is no real title available?)
• scientific article; zbMATH DE number 1990718 (Why is no real title available?)
• scientific article; zbMATH DE number 7274067 (Why is no real title available?)
• The Erdős-Gsyárfás conjecture holds for \(P_{10}\)-free graphs
• On the choice number of claw-free perfect graphs
• The path partition conjecture is true for claw-free graphs
• Erdős-Gyárfás conjecture for some families of Cayley graphs
• Classes of cubic graphs containing cycles of integer-power lengths
• scientific article; zbMATH DE number 1735729 (Why is no real title available?)
• scientific article; zbMATH DE number 1472112 (Why is no real title available?)
• scientific article; zbMATH DE number 7204318 (Why is no real title available?)
• Erdős-Gyárfás conjecture for \(P_8\)-free graphs
• On \(q\)-power cycles in cubic graphs
• On the Erdős-Gyárfás conjecture for some Cayley graphs
• On 2-power unicyclic cubic graphs
• Double-critical graph conjecture for claw-free graphs

This page was built for publication: On the Erdős-Gyárfás conjecture in claw-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2509554)