Records 
Author 
de Figueiredo, C.M.H.; de Mello, C.P.; Ortiz, C. 
Title 
Edge colouring reduced indifference graphs 
Type 

Year 
2000 
Publication 
Lecture Notes in Computer Sciences 
Abbreviated Journal 
Lect. Notes Comput. Sc. 
Volume 
1776 
Issue 

Pages 
145153 
Keywords 

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 neighbourhoodover full indifference graphs proving that a reduced indifference graph cannot be neighbourhoodoverfull. We show that the chromatic index for all reduced indifference graphs is the maximum degree. 
Address 

Corporate Author 

Thesis 

Publisher 

Place of Publication 

Editor 

Language 

Summary Language 

Original Title 

Series Editor 

Series Title 

Abbreviated Series Title 

Series Volume 

Series Issue 

Edition 

ISSN 
03029743 
ISBN 

Medium 

Area 

Expedition 

Conference 
Latin 2000: Theoretical Informaticsture Notes in Computer Science 
Notes 
WOS:000165335400016 
Approved 

Call Number 
UAI @ eduardo.moreno @ 
Serial 
25 
Permanent link to this record 



Author 
de Figueiredo, C.M.H.; Meldanis, J.; de Mello, C.P.; Ortiz, C. 
Title 
Decompositions for the edge colouring of reduced indifference graphs 
Type 

Year 
2003 
Publication 
Theoretical Computer Science 
Abbreviated Journal 
Theor. Comput. Sci. 
Volume 
297 
Issue 
13 
Pages 
145155 
Keywords 

Abstract 
The chromatic index problemfinding the minimum number of colours required for colouring the edges of a graphis 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. We present new positive evidence for the conjecture: every non neighbourhoodoverfull indifference graph can be edge coloured with maximum degree colours. 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 neighbourhoodoverfull indifference graphs proving that a reduced indifference graph cannot be neighbourhoodoverfull. We show that the chromatic index for all reduced indifference graphs is the maximum degree. We present two decomposition methods for edge colouring reduced indifference graphs with maximum degree colours. (C) 2002 Elsevier Science B.V. All rights reserved. 
Address 

Corporate Author 

Thesis 

Publisher 

Place of Publication 

Editor 

Language 

Summary Language 

Original Title 

Series Editor 

Series Title 

Abbreviated Series Title 

Series Volume 

Series Issue 

Edition 

ISSN 
03043975 
ISBN 

Medium 

Area 

Expedition 

Conference 

Notes 
WOS:000181732700008 
Approved 

Call Number 
UAI @ eduardo.moreno @ 
Serial 
24 
Permanent link to this record 