Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/241606
Type: Artigo de periódico
Title: Edge-coloring Of Split Graphs
Author: de Almeida
Sheila Morais; de Mello
Celia Picinin; Morgana
Aurora
Abstract: The Classification Problem is the problem of deciding whether a simple graph has chromatic index equals to Delta or Delta + 1, where Delta is the maximum degree of the graph. It is known that to decide if a graph has chromatic index equals to Delta is NP-complete. A split graph is a graph whose vertex set admits a partition into a stable set and a clique. The chromatic indexes for some subsets of split graphs, such as split graphs with odd maximum degree and split-indifference graphs, are known. However, for the general class, the problem remains unsolved. In this paper we exhibit a new subset of split graphs with even maximum degree that have chromatic index equal to Delta. Moreover, we present polynomial time algorithms to perform an edge-coloring and to recognize these graphs.
Subject: Chromatic Index
Country: WINNIPEG
Editor: CHARLES BABBAGE RES CTR
Rights: fechado
Identifier DOI: 
Address: http://www.sciencedirect.com/science/article/pii/S1571065308000061
Date Issue: 2015
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File SizeFormat 
wos_000351784700032.pdf221.44 kBAdobe PDFView/Open


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