pith. machine review for the scientific record. sign in

arxiv: 1010.2472 · v3 · submitted 2010-10-12 · 💻 cs.DM

Recognition: unknown

Three-coloring triangle-free graphs on surfaces I. Extending a coloring to a disk with one triangle

Authors on Pith no claims yet
classification 💻 cs.DM
keywords coloringlengthcoloredexactlytrianglevertexadjacentcolor
0
0 comments X
read the original abstract

Let G be a plane graph with exactly one triangle T and all other cycles of length at least 5, and let C be a facial cycle of G of length at most six. We prove that a 3-coloring of C does not extend to a 3-coloring of G if and only if C has length exactly six and there is a color x such that either G has an edge joining two vertices of C colored x, or T is disjoint from C and every vertex of T is adjacent to a vertex of C colored x. This is a lemma to be used in a future paper of this series.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.