| |
|
|
Abstract: We study backbone colorings, a variation on classical vertex colorings: Given a graph $G$ and a spanning subgraph $H$ of $G$ (the backbone of $G$), a backbone coloring for $G$ and $H$ is a proper vertex $k$-coloring of $G$ in which the colors assigned to adjacent vertices in $H$ differ by at least $2$. The minimal $k\in \mathbb{N}$ for which such a coloring exists is called the backbone chromatic number of $G$. We show that for a graph $G$ of maximum degree $\Delta$ with the backbone graph being a $d$-degenerated subgraph of $G$, the backbone chromatic number is at most $\Delta + d + 1$ and moreover, in the case when the backbone graph being a matching we prove that backbone chromatic number is at most $\Delta+ 1$. We also present examples where these bounds are attained. Finally, the asymptotic behavior of the backbone chromatic number is studied regarding the degrees of $G$ and $H$. We prove for any sparse graph $G$ that if the maximum degree of a backbone graph is small compared to the maximum degree of $G$, then the backbone chromatic number is at most $\Delta(G)-\sqrt{\Delta(G)}$. Contact the authors: jozef.miskuf@upjs.sk, tancer@kam.mff.cuni.cz Download PDF version of the preprint. |