A survey and strengthening of Erdős-Gyarfas conjecture

MaRDI QIDQ1677333zbMATH OpenFDO

Authors Mushtaq A. Shah, Mridula Purohit, M. H. Gulzar

Publication date 20 November 2017

Published in Advances in Mathematics. Scientific Journal (Search for Journal in Brave)

zbMATH Keywords

connected graphcubic graphcycles of graphErdős-Gyarfas conjecturethree connected graphs

Mathematics Subject Classification ID

Vertex degrees (05C07) Distance in graphs (05C12) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Connectivity (05C40)

Review text

Erdős-Gyarfas conjecture states that every graph with minimum degree 3 contains a simple cycle whose length is a power of 2. In this paper, the authors prove that if a graph \(G\) of order \(n\) having \(n-2\) vertices of degree 3 and two vertices of degree 2 does not contain a cycle of length \(2^n\) and the distance between the vertices of degree 2 is \(n/2+1\) and this number is odd, then there exists a cubic graph which does not contain a cycle of length \(2^n\).

Recommendations

• The Erdős-Hajnal conjecture. A survey
• scientific article; zbMATH DE number 24365
• A strengthening of the Erdős-Szekeres theorem
• A strengthening of Erdős-Gallai theorem and proof of Woodall's conjecture
• A note on the Erdős-Straus conjecture
• A note on the Erdős-Straus conjecture
• On a Conjecture of Erdős, Gallai, and Tuza
• On the Erdos-Straus conjecture
• scientific article; zbMATH DE number 1047742
• A generalization of the Erdős-Surányi problem

Cited in

(14)

• Erdős-Gyárfás conjecture for some families of Cayley graphs
• Graphs without proper subgraphs of minimum degree 3 and short cycles
• Erdős-Gyárfás conjecture for cubic planar graphs
• Erdős-Gyárfás conjecture for \(P_8\)-free graphs
• A strengthening of Erdős-Gallai theorem and proof of Woodall's conjecture
• scientific article; zbMATH DE number 1990718 (Why is no real title available?)
• scientific article; zbMATH DE number 1472112 (Why is no real title available?)
• scientific article; zbMATH DE number 6930495 (Why is no real title available?)
• On the Erdős-Gyárfás conjecture for some Cayley graphs
• Classes of cubic graphs containing cycles of integer-power lengths
• On \(q\)-power cycles in cubic graphs
• On 2-power unicyclic cubic graphs
• scientific article; zbMATH DE number 7651162 (Why is no real title available?)
• The Erdős-Gsyárfás conjecture holds for \(P_{10}\)-free graphs

This page was built for publication: A survey and strengthening of Erdős-Gyarfas conjecture

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