Premium
Extensions of Fractional Precolorings Show Discontinuous Behavior
Author(s) -
Heuvel Jan,
Král' Daniel,
Kupec Martin,
Sereni JeanSébastien,
Volec Jan
Publication year - 2014
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21787
Subject(s) - mathematics , combinatorics , graph , integer (computer science) , upper and lower bounds , function (biology) , discrete mathematics , mathematical analysis , evolutionary biology , computer science , biology , programming language
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 .