Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/77767
Type: Artigo de periódico
Title: Total-chromatic number and chromatic index of dually chordal graphs
Author: de Figueiredo, CMH
Meidanis, J
de Mello, CP
Abstract: Given a graph G and a vertex nu, a vertex u is an element of N(nu) is a maximum neighbor of nu if for all w is an element of N(nu) we have N(zu) subset of or equal to N(u), where N(nu) denotes the neighborhood of nu in G. A maximum neighborhood elimination order of G is a linear order nu(1), nu(2),..., nu(n) on its vertex set such that there is a maximum neighbor of v(i) in the subgraph G[v(1),..., v(i)]. A graph is dually chordal if it admits a maximum neighborhood elimination order. Alternatively, a graph is dually chordal if it is the clique graph of a chordal graph. The class of dually chordal graphs generalizes known subclasses of chordal graphs such as doubly chordal graphs, strongly chordal graphs, interval graphs, and indifference graphs. We prove that Vizing's total-color conjecture holds for dually chordal graphs. We describe a new heuristic that Fields an exact total coloring for even maximum degree dually chordal graphs and an exact edge coloring for odd maximum degree dually chordal graphs. (C) 1999 Elsevier Science B.V. All rights reserved.
Subject: algorithms
graph algorithms
chordal graphs
total coloring
edge coloring
clique graphs
maximum neighborhood ordering
Country: Holanda
Editor: Elsevier Science Bv
Rights: fechado
Identifier DOI: 10.1016/S0020-0190(99)00050-2
Date Issue: 1999
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
WOS000081322500006.pdf75.69 kBAdobe PDFView/Open


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