A tight minimum-degree condition guaranteeing that every \C₅,C₇,C₉,C₁₁\-free graph is 3-colorable

DOI10.1016/J.DISC.2026.115369MaRDI QIDQ7326071zbMATH OpenFDO

Authors Xiaoli Yuan, Yuejian Peng

Publication date 8 September 2026

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DISC.2026.115369

Mathematics Subject Classification ID

Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15)

Cites work

• 4-chromatic graphs with large odd girth
• Beyond chromatic threshold via (p,q)-theorem, and blow-up phenomenon
• Cycles with consecutive odd lengths
• Dense graphs with small clique number
• Homomorphism thresholds for odd cycles
• Minimum degree stability of \({C}_{2k+1}\)-free graphs
• ODD Cycles of Specified Length in Non-Bipartite Graphs
• On a valence problem in extremal graph theory
• On maximal paths and circuits of graphs
• On the chromatic number of pentagon-free graphs of large minimum degree
• On the chromatic number of triangle-free graphs of large minimum degree
• On the connection between chromatic number, maximal clique and minimal degree of a graph
• On the structure of dense graphs with bounded clique number
• On the Structure of Graphs with Given Odd Girth and Large Minimum Degree
• On the structure of triangle-free graphs of large minimum degree
• The chromatic profile of locally bipartite graphs
• The chromatic profile of locally colourable graphs
• The chromatic thresholds of graphs
• The homomorphism threshold of \({C_3, C_5}\)-free graphs
• Tight bound on the minimum degree to guarantee graphs forbidding some odd cycles to be bipartite
• Triangle-free four-chromatic graphs

This page was built for publication: A tight minimum-degree condition guaranteeing that every \(\{C_5,C_7,C_9,C_{11}\}\)-free graph is 3-colorable

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