Circular Coloring and Fractional Coloring in Planar Graphs

2020/07/01 by Hu, Xiaolan, Li, Jiaao
#05C10 #05C15 #05C38 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2007.00182

Abstract

We study the following Steinberg-type problem on circular coloring: for an odd integer k≥ 3, what is the smallest number f(k) such that every planar graph of girth k without cycles of length from k+1 to f(k) admits a homomorphism to the odd cycle C_k (or equivalently, is circular (k,(k-1)/(2))-colorable). Known results and counterexamples on Steinberg's Conjecture indicate that f(3)∈\6,7\. In this paper, we show that f(k) exists if and only if k is an odd prime. Moreover, we prove that for any prime p≥ 5, p²-(5)/(2)p+(3)/(2)≤ f(p)≤ 2p²+2p-5. We conjecture that f(p)≤ p²-2p, and observe that the truth of this conjecture implies Jaeger's conjecture that every planar graph of girth 2p-2 has a homomorphism to C_p for any prime p≥ 5. Supporting this conjecture, we prove a related fractional coloring result that every planar graph of girth k without cycles of length from k+1 to \lfloor(22k)/(3)\rfloor is fractional (k:(k-1)/(2))-colorable for any odd integer k≥ 5.

Related

• Planar Graphs of Odd-Girth at Least 9 are Homomorphic to the Petersen Graph
• Planar Graphs with Homomorphisms to the 9-cycle
• Fractional coloring of planar graphs of girth five
• The proof of Steinberg's three coloring conjecture
• A relaxation of Steinberg's Conjecture