On L(2, 1) -coloring split, chordal bipartite, and weakly chordal graphs

摘要

An 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, λ is the minimum range of colors for which there exists a λ-coloring of 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) 586-595] states that λ is at most ~(Δ2), where Δ is the maximum degree of a vertex in 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.