Graph color extensions: When Hadwiger's conjecture and embeddings help
type: Item
instance of: scholarly article
title: Graph color extensions: When Hadwiger's conjecture and embeddings help
zbMATH Open document ID: 1005.05017
author: Michael O. Albertson
author: Joan P. Hutchinson
published in: The Electronic Journal of Combinatorics
publication date: 2002-09-22T00:00:00Z
full work available at URL: https://eudml.org/doc/122366
full work available at URL: v9i1r37.html
review text: 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.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 1803674
MaRDI profile type: Publication
Recommended article: A structural theorem on embedded graphs and its application to colorings
Recommended article: Extending graph colorings
Recommended article: Extremal graphs in some coloring problems
Recommended article: Q4071274
Recommended article: On simultaneous colorings of embedded graphs
Recommended article: Extending partial colorings of graphs
Recommended article: Color refinement, homomorphisms, and hypergraphs
Recommended article: Coloring Sums of Extensions of Certain Graphs
Recommended article: Q4668721
Recommended article: Edge colorings of embedded graphs
description: scientific article; zbMATH DE number 1803674