Fractional Coloring Planar Graphs under Steinberg-type Conditions

作者：Hu, Xiao Lan; Li, Jia Ao^*

来源：ACTA MATHEMATICA SINICA-ENGLISH SERIES, 2023, 39(5): 904-922.

DOI：10.1007/s10114-022-1085-7

• Fractional coloring
• circular coloring
• planar graphs
• girth
• homomorphism

A Steinberg-type conjecture on circular coloring is recently proposed that for any prime p >= 5, every planar graph of girth p without cycles of length from p + 1 to p(p - 2) is C-p-colorable (that is, it admits a homomorphism to the odd cycle C-p). The assumption of p >= 5 being prime number is necessary, and this conjecture implies a special case of Jaeger's Conjecture that every planar graph of girth 2p - 2 is C-p-colorable for prime p >= 5. In this paper, combining our previous results, we show the fractional coloring version of this conjecture is true. Particularly, the p = 5 case of our fractional coloring result shows that every planar graph of girth 5 without cycles of length from 6 to 15 admits a homomorphism to the Petersen graph.

• 单位
  南开大学