Extensions of Fractional Precolorings Show Discontinuous Behavior. Issue 4 (13th February 2014) - van den Heuvel, Jan; Král', Daniel; Kupec, Martin; Sereni, Jean‐Sébastien; Volec, Jan
Abstract We study the following problem: given a real number k and an integer d, what is the smallest ε such that any fractional <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh1fd11d0p" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />(k+ɛ)</alternatives>‐precoloring of vertices at pairwise distances at least d of a fractionally k‐colorable graph can be extended to a fractional <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh1fd11d17" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />(k+ɛ)</alternatives>‐coloring of the whole graph? The exact values of ε were known for <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh1fd11cx2" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />k∈{2}∪[3, ∞)</alternatives> and any d. We determine the exact values of ε for <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh1fd11czm" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />k∈(2, 3)</alternatives> if <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh1fd11d4w" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />d=4</alternatives>, and <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh1fd11d5f" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />k∈[2.5, 3)</alternatives> if <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh1fd11d2s" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />d=6</alternatives>, and give upper bounds for <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh1fd11d3b" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />k∈(2, 3)</alternatives> if <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh1fd11d9n" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />d=5, 7</alternatives>, and <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh1fd11jk4" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />k∈(2, 2.5)</alternatives> if <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh1fd11jmp" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />d=6</alternatives>. Surprisingly, ε viewed as a function of k is discontinuous for all those values of d.