Premium
Extending colorings of locally planar graphs
Author(s) -
Albertson Michael O.,
Hutchinson Joan P.
Publication year - 2001
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/1097-0118(200102)36:2<105::aid-jgt5>3.0.co;2-h
Subject(s) - combinatorics , mathematics , eulerian path , planar graph , edge coloring , graph , chromatic scale , discrete mathematics , graph power , line graph , pure mathematics , lagrangian
Suppose G is a graph embedded in S g with width (also known as edge width) at least 264(2 g −1). If P ⊆ V(G) is such that the distance between any two vertices in P is at least 16, then any 5‐coloring of P extends to a 5‐coloring of all of G . We present similar extension theorems for 6‐ and 7‐chromatic toroidal graphs, for 3‐colorable large‐width graphs embedded on S g with every face even‐sided, and for 4‐colorable large‐width Eulerian triangulations. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 105–116, 2001