Between 2- and 3-colorability

2014/04/19 by Frieze, Alan, Pegden, Wesley
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1404.4987

Abstract

We consider the question of the existence of homomorphisms between G_n,p and odd cycles when p=c/n, 1

Related

• A reduction of the "cycles plus K₄'s" problem
• On Colorings of Graph Powers
• Obstructions for homomorphisms to odd cycles in series-parallel graphs
• Graphs with large minimum degree and no small odd cycles are 3-colourable
• Planar Graphs with Homomorphisms to the 9-cycle