z-logo
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 .

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here
Accelerating Research

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom