Extensions of Fractional Precolorings show Discontinuous Behavior

Original · EN

We study the following problem: given a real number k and integer d, what is the smallest epsilon such that any fractional (k+epsilon)-precoloring of vertices at pairwise distances at least d of a fractionally k-colorable graph can be extended to a fractional (k+epsilon)-coloring of the whole graph? The exact values of epsilon were known for k=2 and k≥3 and any d. We determine the exact values of epsilon 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, epsilon viewed as a function of k is discontinuous for all those values of d.