Cycle lengths and chromatic number of graphs

DOI10.1016/J.DISC.2003.11.055MaRDI QIDQ1883263zbMATHOpenAlexFDO

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

zbMATH Keywords

graphchromatic numbercycle length

Mathematics Subject Classification ID

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

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

Cites work

• scientific article; zbMATH DE number 5145350 (Why is no real title available?)
• scientific article; zbMATH DE number 4164941 (Why is no real title available?)
• Colouring Graphs with Prescribed Induced Cycle Lengths
• Graph theory
• Graphs with \(k\) odd cycle lengths

Cited in

(26)

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

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)