Colouring Graphs with Prescribed Induced Cycle Lengths

DOI10.7151/DMGT.1149MaRDI QIDQ4542873zbMATH OpenOpenAlexFDO

Authors Bert Randerath, Ingo Schiermeyer

Publication date 7 January 2003

Published in Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.7151/dmgt.1149

zbMATH Keywords

\(\chi\)-binding functionchromatic numberpolynomial time algorithms

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Coloring graphs without short cycles and long induced paths
• 3-colourability and forbidden subgraphs
• On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
• Colouring square-free graphs without long induced paths
• Three-colourability and forbidden subgraphs. II: Polynomial algorithms

Cited in

(8)

• Colourings of graphs with two consecutive odd cycle lengths
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• On the connection between the chromatic number of a graph and the number of cycles covering a vertex or an edge
• Cycle lengths and chromatic number of graphs
• Coloring graphs with no even hole \(\geqslant 6\): the triangle-free case
• Coloring graphs without short cycles and long induced paths
• scientific article; zbMATH DE number 1305541 (Why is no real title available?)
• Colouring of cycles in the de bruijn graphs

This page was built for publication: Colouring Graphs with Prescribed Induced Cycle Lengths

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