On coloring numbers of graph powers

Abstract

The weak $r$-coloring numbers $wco{l}_r(G)$ of a graph $G$ were introduced by the first two authors as a generalization of the usual coloring number $col(G)$, and have since found interesting theoretical and algorithmic applications. This has motivated researchers to establish strong bounds on these parameters for various classes of graphs. Let $G^p$ denote the $p$-th power of $G$. We show that, all integers $p>0$ and $\Delta \ge 3$ and graphs $G$ with $\Delta (G)\le \Delta$ satisfy $col(G^p)\in O(p\cdot wco{l}_{\lceil p/2\rceil }(G)(\Delta -1{)}^{\lfloor p/2\rfloor })$; for fixed tree width or fixed genus the ratio between this upper bound and worst case lower bounds is polynomial in $p$. For the square of graphs $G$, we also show that, if the maximum average degree $2k-2<mad(G)\le 2k$, then $col(G^2)\le (2k-1)\Delta (G)+2k+1$.

9 pages