Publication details
Coloring powers of chordal graphs
| Authors | |
|---|---|
| Year of publication | 2005 |
| Type | Article in Periodical |
| Magazine / Source | SIAM Journal on Discrete Mathematics |
| Citation | |
| Doi | http://dx.doi.org/10.1137/S0895480103424079 |
| 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. |