zbMATH — the first resource for mathematics

Precoloring extension for \(K_4\)-minor-free graphs. (English) Zbl 1229.05155
Summary: Let \(G=(V, E)\) be a graph where every vertex \(v\in V\) is assigned a list of available colors \(L(v)\). We say that \(G\) is list colorable for a given list assignment if we can color every vertex using its list such that adjacent vertices get different colors. If \(L(v)=\{1,\dots , k\}\) for all \(v\in V\) then a corresponding list coloring is nothing other than an ordinary \(k\)-coloring of \(G\). Assume that \(W\subseteq V\) is a subset of \(V\) such that \(G[W]\) is bipartite and each component of \(G[W]\) is precolored with two colors taken from a set of four. The minimum distance between the components of \(G[W]\) is denoted by \(d(W)\). We will show that if \(G\) is \(K_4\)-minor-free and \(d(W)\geq 7\), then such a precoloring of \(W\) can be extended to a 4-coloring of all of \(V\). This result clarifies a question posed in 10. Moreover, we will show that such a precoloring is extendable to a list coloring of \(G\) for outerplanar graphs, provided that \(|L(v)|=4\) for all \(v\in V\setminus W \) and \(d(W)\geq 7\). In both cases the bound for \(d(W)\) is best possible.

05C35 Extremal problems in graph theory
05C05 Trees
05C83 Graph minors
05C38 Paths and cycles
05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[1] Albertson, You can’t paint yourself into a corner, J Combin Theory Ser B 73 pp 189– (1998) · Zbl 0910.05026
[2] Albertson, Extending colorings of locally planar graphs, J Graph Theory 36 pp 105– (2001) · Zbl 0971.05043
[3] Albertson, Graph color extensions: When embedding helps, Electron J Combin 9 (2002)
[4] Albertson, Extending precolorings of subgraphs of locally planar graphs, European J Combin 25 pp 863– (2004) · Zbl 1050.05044
[5] Albertson, Precoloring extension of Brooks’ Theorem, SIAM J Discrete Math 18 pp 542– (2004)
[6] Albertson, Extending graph colorings, J Combin Theory Ser B 77 pp 83– (1999) · Zbl 1024.05027
[7] Albertson, Extending graph colorings using no extra colors, Discrete Math 234 pp 125– (2001) · Zbl 0999.05030
[8] Axenovich, A note on graph coloring extensions and list colorings, Electron J Combin 10 (2003) · Zbl 1017.05041
[9] P. Erdös, A. L. Rubin, and H. Taylor, Choosability in graphs, Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing (Humboldt State University, Arcata, CA, 1979), Congress. Numer. XXVI (Utilitas Math., Winnipeg, 1980),125-157.
[10] Hutchinson, Distance constraints in graph color extensions, J Combin Theory Ser B 97 pp 501– (2007) · Zbl 1117.05042
[11] Hutchinson, personal communication (2005)
[12] Vizing, Coloring the vertices of a graph in prescribed colors (Russian), Diskret Analiz No. 29 Metody Diskret Anal v Teorii Kodov i Shem pp 3– (1976)
[13] Voigt, Precoloring extension for 2-connected graphs, SIAM J Discrete Math 21 258 pp 258– (2007) · Zbl 1139.05320
[14] Voigt, Precoloring extension for 2-connected graphs with maximum degree three, Discrete Math (2008) · Zbl 1209.05102
[15] West, Introduction to Graph Theory (1996) · Zbl 0845.05001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.