toggle visibility Search & Display Options

Select All    Deselect All
 |   | 
  Record Links
Author (up) de Figueiredo, C.M.H.; Meldanis, J.; de Mello, C.P.; Ortiz, C. pdf  doi
  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 1-3 Pages 145-155  
  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. We present new positive evidence for the conjecture: every non neighbourhood-overfull 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 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. We present two decomposition methods for edge colouring reduced indifference graphs with maximum degree colours. (C) 2002 Elsevier Science B.V. All rights reserved.  
  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 0304-3975 ISBN Medium  
  Area Expedition Conference  
  Notes WOS:000181732700008 Approved  
  Call Number UAI @ eduardo.moreno @ Serial 24  
Permanent link to this record
Select All    Deselect All
 |   | 

Save Citations:
Export Records: