Title | ||
---|---|---|
Five-list-coloring graphs on surfaces III. One list of size one and one list of size two. |
Abstract | ||
---|---|---|
Let G be a plane graph with outer cycle C and let (L(v):v∈V(G)) be a family of non-empty sets. By an L-coloring of G we mean a (proper) coloring ϕ of G such that ϕ(v)∈L(v) for every vertex v of G. Thomassen proved that if v1,v2∈V(C) are adjacent, L(v1)≠L(v2), |L(v)|≥3 for every v∈V(C)−{v1,v2} and |L(v)|≥5 for every v∈V(G)−V(C), then G has an L-coloring. What happens when v1 and v2 are not adjacent? Then an L-coloring need not exist, but in the first paper of this series we have shown that it exists if |L(v1)|,|L(v2)|≥2. Here we characterize when an L-coloring exists if |L(v1)|≥1 and |L(v2)|≥2. |
Year | DOI | Venue |
---|---|---|
2018 | 10.1016/j.jctb.2017.06.004 | Journal of Combinatorial Theory, Series B |
Keywords | Field | DocType |
Graph,List-coloring,Planar graph | Graph,Discrete mathematics,Combinatorics,Vertex (geometry),List coloring,Mathematics,Lemma (mathematics),Planar graph,Bounded function | Journal |
Volume | ISSN | Citations |
128 | 0095-8956 | 1 |
PageRank | References | Authors |
0.36 | 3 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Luke Postle | 1 | 40 | 15.29 |
Robin Thomas | 2 | 457 | 35.92 |