Circular coloring and fractional coloring in planar graphs

作者：Hu, Xiaolan; Li, Jiaao^*

来源：Journal of Graph Theory, 2022, 99(2): 312-343.

DOI：10.1002/jgt.22742

• planar graphs
• circular coloring
• cycle length
• fractional coloring
• girth

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) is an element of {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(2) - 5/2p + 3/2 <= f (p) <= 2p(2 )+ 2p - 5. @@@ We conjecture that f (p) <= p(2) - 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 [22k/3] is fractional (k : k-1/2)-colorable for any odd integer k >= 5.

• 单位
  南开大学