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

DOI10.7151/DMGT.1732zbMATH Open1295.05135arXiv1109.5398OpenAlexW2592983029WikidataQ123152183 ScholiaQ123152183MaRDI QIDQ2509554FDOQ2509554

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)

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.

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

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

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)

Cites Work

• Graph theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• Some old and new problems in various branches of combinatorics
• Title not available (Why is that?)
• Title not available (Why is that?)
• Unavoidable cycle lengths in graphs

Cited In (16)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)