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

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

2010-10-12

arxiv.org/abs/1010.2472v1

Computer Science

Discrete Mathematics

Scientific paper

Let G be a plane graph with 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.

Affiliated with

Also associated with

No associations

Rating

Three-coloring triangle-free graphs on surfaces I. Extending a coloring to a disk with one triangle does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Three-coloring triangle-free graphs on surfaces I. Extending a coloring to a disk with one triangle, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Three-coloring triangle-free graphs on surfaces I. Extending a coloring to a disk with one triangle will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-608934