A note on graph coloring extensions and list-colorings
The electronic journal of combinatorics, Tome 10 (2003)
Let $G$ be a graph with maximum degree $\Delta \geq 3$ not equal to $K_{\Delta +1}$ and let $P$ be a subset of vertices with pairwise distance, $d(P)$, between them at least $8$. Let each vertex $x$ be assigned a list of colors of size $\Delta$ if $x\in V\setminus P$ and $1$ if $x\in P$. We prove that it is possible to color $V(G)$ such that adjacent vertices receive different colors and each vertex has a color from its list. We show that $d(P)$ cannot be improved. This generalization of Brooks' theorem answers the following question of Albertson positively: If $G$ and $P$ are objects described above, can any coloring of $P$ in at most $\Delta$ colors be extended to a proper coloring of $G$ in at most $\Delta$ colors?
@article{10_37236_1741,
author = {Maria Axenovich},
title = {A note on graph coloring extensions and list-colorings},
journal = {The electronic journal of combinatorics},
year = {2003},
volume = {10},
doi = {10.37236/1741},
zbl = {1017.05041},
url = {http://geodesic.mathdoc.fr/articles/10.37236/1741/}
}
Maria Axenovich. A note on graph coloring extensions and list-colorings. The electronic journal of combinatorics, Tome 10 (2003). doi: 10.37236/1741
Cité par Sources :