Abstract
Let be a plane graph with outer cycle and let be a family of non-empty sets. By an -coloring of we mean a (proper) coloring of such that for every vertex of . Thomassen proved that if are adjacent, , for every and for every , then has an -coloring. What happens when and are not adjacent? Then an -coloring need not exist, but in the first paper of this series we have shown that it exists if . Here we characterize when an -coloring exists if and . This result is a lemma toward a more general theorem along the same lines, which we will use to prove that minimally non--colorable planar graphs with two precolored cycles of bounded length are of bounded size. The latter result has a number of applications which we pursue elsewhere.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.