Publication details

Coloring powers of chordal graphs


KRÁĽ Daniel

Year of publication 2005
Type Article in Periodical
Magazine / Source SIAM Journal on Discrete Mathematics
Keywords chordal graphs; graph powers; graph coloring; L(p,q)-labeling
Description We prove that the kth power G(k) of a chordal graph G with maximum degree Delta is O(root k Delta((k+1)/2))-degenerate for even values of k and O(Delta((k+1)/2))-degenerate for odd values. In particular, this bounds the chromatic number.( Gk) of the kth power of G. The bound proven for odd values of k is the best possible. Another consequence is the bound lambda(p,q)(G) <= [(Delta+1)(3/2)/root(6)] (2q - 1 + Delta(2p - 1) on the least possible span lambda(p,q)(G) of an L(p,q)-labeling for chordal graphs G with maximum degree.. On the other hand, a construction of such graphs with lambda(p,q)(G) >= Omega(Delta(3/2)q+Delta p) is found.

You are running an old browser version. We recommend updating your browser to its latest version.

More info