Extensions of Fractional Precolorings Show Discontinuous Behavior. Issue 4 (13th February 2014) - van den Heuvel, Jan
Abstract We study the following problem: given a real number k and an integer d, what is the smallest ε such that any fractional (k+ɛ)‐precoloring of vertices at pairwise distances at least d of a fractionally k‐colorable graph can be extended to a fractional (k+ɛ)‐coloring of the whole graph? The exact values of ε were known for k∈{2}∪[3, ∞) and any d. We determine the exact values of ε for k∈(2, 3) if d=4, and k∈[2.5, 3) if d=6, and give upper bounds for k∈(2, 3) if d=5, 7, and k∈(2, 2.5) if d=6. Surprisingly, ε viewed as a function of k is discontinuous for all those values of d.