Cycle lengths and chromatic number of graphs

DOI10.1016/j.disc.2003.11.055zbMath1055.05060OpenAlexW2122560436MaRDI QIDQ1883263

Peter Mihók, Ingo Schiermeyer

Publication date: 1 October 2004

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2003.11.055

zbMATH Keywords

graphchromatic numbercycle length

Mathematics Subject Classification ID

Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15)

Related Items (15)

Polynomial algorithms that prove an NP-hard hypothesis implies an NP-hard conclusion ⋮ On the connection between the chromatic number of a graph and the number of cycles covering a vertex or an edge ⋮ Problems on cycles and colorings ⋮ Cycle lengths and minimum degree of graphs ⋮ Congruence of cycle lengths and chromatic number ⋮ Circumference, chromatic number and online coloring ⋮ Coloring digraphs with forbidden cycles ⋮ Subdivisions of four blocks cycles in digraphs with large chromatic number ⋮ Cycles in triangle-free graphs of large chromatic number ⋮ A Strengthening on Odd Cycles in Graphs of Given Chromatic Number ⋮ The extremal function for cycles of length \(\ell\) mod \(k\) ⋮ Hitting subgraphs in \(P_4\)-tidy graphs ⋮ Cycle lengths in expanding graphs ⋮ Cycle lengths modulo \(k\) in expanders ⋮ Cycles and new bounds for the chromatic number

Cites Work

• Graphs with \(k\) odd cycle lengths
• Colouring Graphs with Prescribed Induced Cycle Lengths
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Cycle lengths and chromatic number of graphs