van den Heuvel, Jan, Král', Daniel, Kupec, Martin, Sereni, Jean-Sébastien and Volec, Jan (2014) Extensions of fractional precolorings show discontinuous behavior. Journal of Graph Theory, Volume 77 (Number 4). pp. 299-329. doi:10.1002/jgt.21787 ISSN 0364-9024.

Preview

PDF WRAP_Kral_extenze2.pdf - Accepted Version - Requires a PDF viewer. Download (557Kb) | Preview

Request Changes to record.

Abstract

We study the following problem: given a real number k and an integer d, what is the smallest ε such that any fractional inline image-precoloring of vertices at pairwise distances at least d of a fractionally k-colorable graph can be extended to a fractional inline image-coloring of the whole graph? The exact values of ε were known for inline image and any d. We determine the exact values of ε for inline image if inline image, and inline image if inline image, and give upper bounds for inline image if inline image, and inline image if inline image. Surprisingly, ε viewed as a function of k is discontinuous for all those values of d.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Science, Engineering and Medicine > Science > Mathematics
Library of Congress Subject Headings (LCSH):	Graph theory, Graph coloring
Journal or Publication Title:	Journal of Graph Theory
Publisher:	John Wiley & Sons Ltd.
ISSN:	0364-9024
Official Date:	December 2014
Dates:	Date Event December 2014 Published 13 February 2014 Available 23 May 2013 Submitted
Volume:	Volume 77
Number:	Number 4
Page Range:	pp. 299-329
DOI:	10.1002/jgt.21787
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Date of first compliant deposit:	4 March 2016
Date of first compliant Open Access:	4 March 2016
Funder:	Hubert Curien Program (HCP)
Grant number:	24444XD

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads