Random cubic graphs are not homomorphic to the cycle of size 7

DOI10.1016/j.jctb.2004.11.004zbMath1057.05073arXivmath/0701013OpenAlexW2065484772MaRDI QIDQ1767675

Hamed Hatami

Publication date: 8 March 2005

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0701013

zbMATH Keywords

HomomorphismCubic graphCircular chromatic numberRandom cubic graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15)

Related Items (8)

On the odd girth and the circular chromatic number of generalized Petersen graphs ⋮ A Note on Circular Chromatic Number of Graphs with Large Girth and Similar Problems ⋮ Density and power graphs in graph homomorphism problem ⋮ Circular coloring of random graphs: statistical physics investigation ⋮ Between 2- and 3-colorability ⋮ High-girth cubic graphs are homomorphic to the Clebsch graph ⋮ On colorings of graph powers ⋮ Cuts and bounds

Cites Work

• Regular graphs with no homomorphisms onto cycles
• Aspects of structural combinatorics. (Graph homomorphisms and their use)
• Circular chromatic number: A survey
• Colorings and homomorphisms of degenerate and bounded degree graphs
• Unnamed Item
• Unnamed Item

This page was built for publication: Random cubic graphs are not homomorphic to the cycle of size 7