On L(2,1) L ( 2 , 1 ) -coloring split, chordal bipartite, and weakly chordal graphs ?
An L(2,1) L ( 2 , 1 ) -coloring, or ? ? -coloring, of a graph is an assignment of non-negative integers to its vertices such that adjacent vertices get numbers at least two apart, and vertices at distance two get distinct numbers. Given a graph G G , ? ? is the minimum range of colors for which there exists a ? ? -coloring of G G . A conjecture by Griggs and Yeh [J.R.Griggs, R.K.Yeh, Labelling graphs with a condition at distance 2, SIAM Journal on Discrete Mathematics 5 (1992) 586595] states that ? ? is at most ?2 ? 2 , where ? ? is the maximum degree of a vertex in G G . We prove that this conjecture holds for weakly chordal graphs. Furthermore, we improve the known upper bounds for chordal bipartite graphs, and for split graphs.
1 ) weakly chordal graphs chordal bipartite graphs split graphs l(2 1) l ( 2 1 ) -coloring l(2 1 ) l(2 1 ) l ( 2