Extensions of fractional precolorings show discontinuous behavior
van den Heuvel, J.
, Král', D., Kupec, M., Sereni, J. & Volec, J.
(2014).
Extensions of fractional precolorings show discontinuous behavior.
Journal of Graph Theory,
77(4), 299-329.
https://doi.org/10.1002/jgt.21787
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.
| Item Type | Article |
|---|---|
| Copyright holders | © 2014 Wiley Periodicals, Inc. |
| Departments | LSE > Academic Departments > Mathematics |
| DOI | 10.1002/jgt.21787 |
| Date Deposited | 28 Feb 2014 |
| URI | https://researchonline.lse.ac.uk/id/eprint/55918 |
Explore Further
- https://www.scopus.com/pages/publications/84907942603 (Scopus publication)
- http://onlinelibrary.wiley.com/journal/10.1002/%28... (Official URL)
ORCID: https://orcid.org/0000-0003-0897-9148