Artículos de revistas
Edge-coloring Of Split Graphs
Registro en:
Edge-coloring Of Split Graphs. Charles Babbage Res Ctr, v. 119, p. 363-375 JAN-2015.
0381-7032
WOS:000351784700032
Autor
de Almeida
Sheila Morais; de Mello
Celia Picinin; Morgana
Aurora
Institución
Resumen
Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) 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. 119
363 375 Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) CNPq [140709/2008-8, 306461/2009-9, 482521/2007-4]