Premium
A decomposition for total‐coloring partial‐grids and list‐total‐coloring outerplanar graphs
Author(s) -
Machado Raphael C. S.,
de Figueiredo Celina M. H.
Publication year - 2011
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20424
Subject(s) - combinatorics , total coloring , mathematics , complete coloring , vertex (graph theory) , brooks' theorem , edge coloring , chromatic scale , list coloring , fractional coloring , graph , outerplanar graph , chordal graph , discrete mathematics , 1 planar graph , pathwidth , graph power , line graph
The total chromatic number χ T ( G ) is the least number of colors sufficient to color the elements (vertices and edges) of a graph G in such a way that no incident or adjacent elements receive the same color. In the present work, we obtain two results on total‐coloring. First, we extend the set of partial‐grids classified with respect to the total‐chromatic number, by proving that every 8‐chordal partial‐grid of maximum degree 3 has total chromatic number 4. Second, we prove a result on list‐total‐coloring biconnected outerplanar graphs. If for each element x of a biconnected outerplanar graph G there exists a set L x of colors such that | L uw | = max{ deg ( u ) + 1, deg ( w ) + 1} for each edge uw and | L v | = 7 − δ deg ( v ),3 − 2δ deg ( v ),2 (where δ i,j = 1 if i = j and δ i,j = 0 if i ≠ j ) for each vertex v , then there is a total‐coloring π of graph G such that π( x ) ∈ L x for each element x of G . The technique used in these two results is a decomposition by a cutset of two adjacent vertices, whose properties are discussed in the article. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011