Cycle lengths and chromatic number of graphs

DOI10.1016/J.DISC.2003.11.055zbMATH Open1055.05060OpenAlexW2122560436MaRDI QIDQ1883263FDOQ1883263

Authors: 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

Recommendations

• Cycle length parities and the chromatic number
• The number of shortest cycles and the chromatic uniqueness of a graph
• Cycles and new bounds for the chromatic number
• Cycle lengths and minimum degree of graphs
• On the chromatic number of circulant graphs
• Cycles of given lengths in hypergraphs
• Induced cycles and chromatic number
• Cycles in triangle-free graphs of large chromatic number
• Cycle lengths in planar graphs
• The chromatic polynomial for cycle graphs

zbMATH Keywords

graphchromatic numbercycle length

Mathematics Subject Classification ID

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

Cites Work

• Graph theory
• Title not available (Why is that?)
• Graphs with \(k\) odd cycle lengths
• Colouring Graphs with Prescribed Induced Cycle Lengths
• Title not available (Why is that?)

Cited In (25)

• Even edge colorings of a graph
• Graphs with \(k\) odd cycle lengths
• Congruence of cycle lengths and chromatic number
• The chromatic number of a graph with two odd holes and an odd girth
• Cycle lengths modulo \(k\) in expanders
• Coloring digraphs with forbidden cycles
• Cycles in triangle-free graphs of large chromatic number
• The number of shortest cycles and the chromatic uniqueness of a graph
• Polynomial algorithms that prove an NP-hard hypothesis implies an NP-hard conclusion
• Hitting subgraphs in \(P_4\)-tidy graphs
• Circumference, chromatic number and online coloring
• Cycles and new bounds for the chromatic number
• Cycle length parities and the chromatic number
• On the connection between the chromatic number of a graph and the number of cycles covering a vertex or an edge
• Cycle lengths in expanding graphs
• A Strengthening on Odd Cycles in Graphs of Given Chromatic Number
• Small odd cycles in 4-chromatic graphs
• On the Number of Cycles in a Graph with Restricted Cycle Lengths
• Subdivisions of four blocks cycles in digraphs with large chromatic number
• Graphs with odd cycle lengths 5 and 7 are 3-colorable
• What must and what need not be contained in a graph of uncountable chromatic number?
• The extremal function for cycles of length \(\ell\) mod \(k\)
• Bounds for chromatic number in terms of even-girth and booksize
• Problems on cycles and colorings
• Cycle lengths and minimum degree of graphs

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

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