Graph color extensions: When Hadwiger's conjecture and embeddings help
The electronic journal of combinatorics, Tome 9 (2002)
Suppose $G$ is $r$-colorable and $P \subseteq V(G)$ is such that the components of $G[P]$ are far apart. We show that any $(r+s)$-coloring of $G[P]$ in which each component is $s$-colored extends to an $(r+s)$-coloring of $G$. If $G$ does not contract to $K_5$ or is planar and $s \geq 2$, then any $(r+s-1)$-coloring of $P$ in which each component is $s$-colored extends to an $(r+s-1)$-coloring of $G$. This result uses the Four Color Theorem and its equivalence to Hadwiger's Conjecture for $k = 5$. For $s=2$ this provides an affirmative answer to a question of Thomassen. Similar results hold for coloring arbitrary graphs embedded in both orientable and non-orientable surfaces.
@article{10_37236_1653,
author = {Michael O. Albertson and Joan P. Hutchinson},
title = {Graph color extensions: {When} {Hadwiger's} conjecture and embeddings help},
journal = {The electronic journal of combinatorics},
year = {2002},
volume = {9},
doi = {10.37236/1653},
zbl = {1005.05017},
url = {http://geodesic.mathdoc.fr/articles/10.37236/1653/}
}
Michael O. Albertson; Joan P. Hutchinson. Graph color extensions: When Hadwiger's conjecture and embeddings help. The electronic journal of combinatorics, Tome 9 (2002). doi: 10.37236/1653
Cité par Sources :