Inmetro  >
Metrologia >
Metrologia Científica e Industrial >
Metrologia de Tecnologia da Informação e Comunicações >
DITEL | Artigos publicados em periódicos internacionais >

Please use this identifier to cite or link to this item:

Title: A decomposition for total-coloring partial-grids and list-total-coloring outerplanar graphs
Authors: Machado, Raphael Carlos Santos
Figueiredo, Celina Miraglia Herrera de
Advisors: Rede parcial
Keywords: Teoria dos grafos
Teoria matemática : algoritmo complexo
Total de coloração
Decomposição gráfica
Issue Date: 2011
Citation: MACHADO, Raphael C. S.; FIGUEIREDO, Celina M. H. de. A decomposition for total-coloring partial-grids and list-total-coloring outerplanar graphs. Networks, v. 57, n. 3, p. 261-269, 2011.
Abstract: The total chromatic number χT (G) is the least numberof colors sufficient to color the elements (vertices and edges) of a graphG in such away that no incident or adjacent elements receive the same color. In the presentwork,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 Lx of colors such that |Luw| = max{deg(u) + 1, deg(w) + 1} for each edge uw and |Lv| = 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) ∈ Lx 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.
Description: 9 p. : il.
Document type: Artigo / Article
Unit: Divisão de Metrologia em Telecomunicações - Ditel
Appears in Collections:DITEL | Artigos publicados em periódicos internacionais

Files in This Item:

File Description SizeFormat
Machado_2011.pdf284,71 kBAdobe PDFUnder Embargo

This item is licensed under a Creative Commons License
Creative Commons

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0! DSpace Software Copyright © 2002-2008  The DSpace Foundation - Feedback