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

DOI10.1007/S00373-022-02578-9MaRDI QIDQ2084789zbMATH OpenOpenAlexWikidataFDO

Authors Songling Shan, Yuping Gao

Publication date 13 October 2022

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

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 1735729 (Why is no real title available?)
• scientific article; zbMATH DE number 1472112 (Why is no real title available?)
• 3-colorable subclasses of \(P_8\)-free graphs
• Erdős-Gyárfás conjecture for cubic planar graphs
• Erdős-Gyárfás conjecture for some families of Cayley graphs
• On the Erdős-Gyárfás conjecture for some Cayley graphs
• On the Erdős-Gyárfás conjecture in claw-free graphs
• Some old and new problems in various branches of combinatorics

Cited in

(7)

• Erdős-Gyárfás conjecture for cubic planar graphs
• 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⁸
• scientific article; zbMATH DE number 1472112 (Why is no real title available?)
• Graphs without proper subgraphs of minimum degree 3 and short cycles
• On the Erdős-Gyárfás conjecture for some Cayley graphs

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)