Graph color extensions: When Hadwiger's conjecture and embeddings help (Q698612): Difference between revisions

Summary: 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.