Colorings and homomorphisms of degenerate and bounded degree graphs

DOI10.1016/S0012-365X(00)00245-4zbMath0983.05032OpenAlexW2109191591MaRDI QIDQ5936036

Alexandr V. Kostochka, Jaroslav Nešetřil, P. Smolíková

Publication date: 16 April 2002

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

Full work available at URL: https://doi.org/10.1016/s0012-365x(00)00245-4

zbMATH Keywords

graph coloringhomomorphismgirthcubic graphsdegenerate graphs

Mathematics Subject Classification ID

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

Related Items (11)

On the odd girth and the circular chromatic number of generalized Petersen graphs ⋮ Constraints, MMSNP and expander relational structures ⋮ Colouring, constraint satisfaction, and complexity ⋮ Density and power graphs in graph homomorphism problem ⋮ Circular coloring of random graphs: statistical physics investigation ⋮ Random cubic graphs are not homomorphic to the cycle of size 7 ⋮ High-girth cubic graphs are homomorphic to the Clebsch graph ⋮ Homomorphisms of hexagonal graphs to odd cycles ⋮ A combinatorial constraint satisfaction problem dichotomy classification conjecture ⋮ On colorings of graph powers ⋮ Cuts and bounds

This page was built for publication: Colorings and homomorphisms of degenerate and bounded degree graphs