On \(L(2,1)\)-coloring split, chordal bipartite, and weakly chordal graphs (Q1759841): Difference between revisions

An \(L(2,1)\) coloring of a graph \(G=(V,E)\) is a mapping \(c:V\rightarrow \{0,1,\dots,k\}\) such that \(|c(u)-c(v)| \geq 2\) for any pair \(uv\) of adjacent vertices, and \(c(u) \neq c(v)\) if \(u\) and \(v\) are at a distance 2. Let \(\lambda\) be the smallest number \(k\) for which there exists an \(L(2,1)\) coloring of \(G\). \textit{J.R. Griggs} and \textit{R.K. Yeh} [SIAM J. Discrte Math. 5, No\,4, 586--595 (1992; Zbl 0767.05080)] conjectured that \(\lambda \leq \Delta^{2},\) where \(\Delta \) is the maximum degree of \(G\). In this paper the conjecture is proved for a class of chordal graphs.