A Decomposition for Total-Coloring Partial-Grids and List-Total-Coloring Outerplanar Graphs

作者：Machado Raphael C S^*; de Figueiredo Celina M H

来源：Networks, 2011, 57(3): 261-269.

DOI：10.1002/net.20424

• total-coloring
• list-total-coloring
• graph decompositions
• partial-grids
• outerplanar graphs

The total chromatic number chi(T)(G) is the least number of colors sufficient to color the elements (vertices and edges) of a graph Gin 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-delta(deg(v),3)-2 delta(deg(v),2) (where delta(i,j) = 1 if i = j and delta(i,j) = 0 if i not equal j) for each vertex v, then there is a total-coloring pi of graph G such that pi (x) is an element of 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-5