Extensions of Fractional Precolorings show Discontinuous Behavior
Résumé
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.
Domaines
Combinatoire [math.CO]
Origine : Fichiers produits par l'(les) auteur(s)
Loading...