Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/100111
Type: Artigo de periódico
Title: On Edge-colouring Indifference Graphs
Author: De Figueiredo C.M.H.
Meidanis J.
De Mello C.P.
Abstract: Vizing's theorem states that the chromatic index χ′(G) of a graph G is either the maximum degree Δ(G) or Δ(G) + 1. A graph G is called overfull if \E(G)| > Δ(G)[\V(G)|/2]. A sufficient condition for χ′(G) = Δ(G) + 1 is that G contains an overfull subgraph H with Δ(H) = Δ(G). Plantholt proved that this condition is necessary for graphs with a universal vertex. In this paper, we conjecture that, for indifference graphs, this is also true. As supporting evidence, we prove this conjecture for general graphs with three maximal cliques and with no universal vertex, and for indifference graphs with odd maximum degree. For the latter subclass, we prove that χ′ = Δ.
Editor: 
Rights: fechado
Identifier DOI: 
Address: http://www.scopus.com/inward/record.url?eid=2-s2.0-0031189605&partnerID=40&md5=c1485e478a158b5c6aee094e2a52f144
Date Issue: 1997
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
2-s2.0-0031189605.pdf1.02 MBAdobe PDFView/Open


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