Erdős-Gyárfás conjecture for P₈-free graphs

DOI10.1007/S00373-022-02578-9zbMATH Open1498.05142arXiv2109.01277OpenAlexW4304080595WikidataQ123114416 ScholiaQ123114416MaRDI QIDQ2084789FDOQ2084789

Songling Shan, Yuping Gao

Publication date: 13 October 2022

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: A graph is $P_8$-free if it contains no induced subgraph isomorphic to the path $P_8$ on eight vertices. In 1995, ErdH{o}s and Gy'{a}rf'{a}s conjectured that every graph of minimum degree at least three contains a cycle whose length is a power of two. In this paper, we confirm the conjecture for $P_8$-free graphs by showing that there exists a cycle of length four or eight in every $P_8$-free graph with minimum degree at least three.

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

Recommendations

• A survey and strengthening of Erdős-Gyarfas conjecture
• On the Erdős-Gyárfás conjecture for some Cayley graphs
• Erdős-Gyárfás conjecture for cubic planar graphs
• Publication:4489163
• On the Erdős-Gyárfás conjecture in claw-free graphs

zbMATH Keywords

cycle\(P_8\)-free graphErdős-Gyárfás conjecture

Mathematics Subject Classification ID

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

Cites Work

• Some old and new problems in various branches of combinatorics
• Erdős-Gyárfás conjecture for cubic planar graphs
• On the Erdős-Gyárfás conjecture in claw-free graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Erdős-Gyárfás conjecture for some families of Cayley graphs
• 3-Colorable Subclasses of $P_8$-Free Graphs
• Title not available (Why is that?)

Cited In (4)

• The Erdős-Gsyárfás conjecture holds for \(P_{10}\)-free graphs
• Extremal \(P_8\)-free/\(P_9\)-free planar graphs
• Pósa's conjecture for graphs of order at least 2 × 10⁸
• Title not available (Why is that?)

This page was built for publication: Erdős-Gyárfás conjecture for \(P_8\)-free graphs

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