Graph color extensions: When Hadwiger's conjecture and embeddings help (Q698612): Difference between revisions
From MaRDI portal
Created a new Item |
Set profile property. |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 02:00, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Graph color extensions: When Hadwiger's conjecture and embeddings help |
scientific article |
Statements
Graph color extensions: When Hadwiger's conjecture and embeddings help (English)
0 references
22 September 2002
0 references
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.
0 references