2-distance coloring of sparse graphs (Q6486785)

For an undirected graph \(G,\) let \(\Delta (G)\) denote the maximum degree of \(G\) and \(\operatorname{mad}(G)\) denote the maximum of \(\sum_{v\in V(H)}d_H(v)/|V(H)|\) taken over all subgrahps \(H\) of \( G\). A 2-distance \(k\)-coloring assigns a color from the set of \(k\) colors to any vertex of \(G\) such that two vertices have different colors if they are adjacent or they have a common neighbor. If a set of \(k\) colors is assigned to every vertex and its color is taken from this set then 2-distance coloring is 2-distance \(k\)-list coloring and, moreover, if distinct neighbors of a vertex have distinct colors then we talk about injective 2-distance \(k\)-list coloring. Let \(\chi^2(G)\) denote the smallest \(k\) such that \(G\) admits 2-distance \(k\)-coloring and \(\chi_l^2(G)\) denote the smallest \(k\) such that \(G\) admits \(2\)-distance \(k\)-list coloring. It is proved that if \(G\) is a graph such that \(\Delta (G)\geq 4\) and \(\operatorname{mad}(G)<\frac 7 3\) then \(\chi^2(G)=\Delta (G)+1\) (these bounds are optimal), if \(G\) is a graph such that \(\Delta (G)\geq 5\) and \(\operatorname{mad}(G)<\frac {12}5\) or \(\Delta (G)\geq 6\) and \(\operatorname{mad}(G)<\frac 52\) or \(\Delta (G)\geq 8\) and \(\operatorname{mad}(G)<\frac {18}7\) then \(\chi^2_l(G)=\Delta (G)+1\) (and there exists an injective \(2\)-distance \((\Delta (G)+1)\)-list coloring). There exist functions \(f\) and \(h\) such that if \(G\) is a graph with \(\operatorname{mad}(G)<\frac {14}5-\epsilon\) and \(\Delta (G)\geq f(\epsilon )\) then \( \chi^2_l(G)=\Delta (G)+1\) and if \(G\) is a graph with \(\operatorname{mad}(G)<4-\epsilon\) then \(\chi^2_l(G)\leq\Delta (G)+h (\epsilon )\). Several consequences for planar graphs are derived. The presented proofs yield algorithms for the solution of these problems.