Extensions of fractional precolorings show discontinuous behavior (Q6486791)

Let \(G\) be a graph, and \(k>0\) a rational number. Then a fractional \(k\)-coloring of \(G\) is a function mapping vertices of \(G\) to measure 1 subsets of \([0,k)\), with the property that adjacent vertices are mapped to disjoint subsets. If \(W\) is a set of nonadjacent vertices in \(G\), then a \(k\) -precoloring of \(W\) is an arbitrary function mapping elements of \(W\) to measure 1 subsets of \([0,k)\). The problem of extending precolorings to colorings was investigated in recent work of \textit{D. Král'} et al. [SIAM J. Discrete Math. 26, No. 2, 647--660 (2012; Zbl 1248.05070)]. For each rational number \(k\geq2\) and each integer \(d\geq3\), they defined \(g(k,d)\) to be the infimum of the values of \(\varepsilon>0\) such that for every fractionally \(k\)-colorable graph \(G\) and every subset \(W\subseteq V(G)\) whose elements are separated by distances \(\geq d\), every \((k+\varepsilon)\)-precoloring of \(W\) extends to a \((k+\varepsilon )\)-coloring of \(G\). They showed that \(g(k,3)=1\) for all \(k\geq2\), and they gave four formulas for \(g(k,d)\) when \(k\in\{2\}\cup(3,\infty)\) and \(d\geq4\); there is a different formula for each congruence class of \(d\) modulo 4.NEWLINENEWLINENEWLINEThe paper under review concerns some aspects of the behavior of \(g(k,d)\), not presented by D. Král' et al. [loc. cit.]. In particular, the authors determine \(g(k,4)\) for \(k\in(2,3)\) and \(g(k,6)\) when \(k\in(2.5,3)\), and they provide upper bounds for \(g(k,d)\) when \(k\in(2,3)\) and \(d\in\{5,7\}\). It turns out that \(g(k,4)\) and \(g(k,5)\) are discontinuous at \(k=3\), and \(g(k,6)\) and \(g(k,7)\) are discontinuous at both \(k=2.5\) and \(k=3\).NEWLINENEWLINEThe paper ends with several conjectures regarding the behavior of \(g(k,d)\), including the conjecture that for every integer \(d>3\), \(g(k,d)\) is a discontinuous function of \(k\).