Please use this identifier to cite or link to this item:
Type: Artigo de evento
Title: Edge Colouring Reduced Indifference Graphs
Author: De Figueiredo C.M.H.
De Mello C.P.
Ortiz C.
Abstract: The chromatic index problem - finding the minimum number of colours required for colouring the edges of a graph - is still unsolved for indifference graphs, whose vertices can be linearly ordered so that the vertices contained in the same maximal clique are consecutive in this order. Two adjacent vertices are twins if they belong to the same maximal cliques. A graph is reduced if it contains no pair of twin vertices. A graph is overfull if the total number of edges is greater than the product of the maximum degree by [n/2], where n is the number of vertices. We give a structural characterization for neighbourhood-overfull indifference graphs proving that a reduced indifference graph cannot be neighbourhood-overfull. We show that the chromatic index for all reduced indifference graphs is the maximum degree. © Springer-Verlag Berlin Heidelberg 2000.
Rights: fechado
Identifier DOI: 10.1007/10719839_16
Date Issue: 2000
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
There are no files associated with this item.

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