Artículos de revistas
Edge Coloring Of Split Graphs
Registro en:
Electronic Notes In Discrete Mathematics. , v. 30, n. C, p. 21 - 26, 2008.
15710653
10.1016/j.endm.2008.01.005
2-s2.0-39149083038
Autor
Almeida S.M.
de Mello C.P.
Morgana A.
Institución
Resumen
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. This paper presents new results about the classification problem for split graphs as a contribution in the direction of solving the entire problem for this class. © 2008 Elsevier B.V. All rights reserved. 30 C 21 26 Cai, L., Ellis, J.A., NP-completeness of edge-colouring some restricted graphs (1991) Discrete Applied Mathematics, 30, pp. 15-27 Chen, B.-L., Fu, H.-L., Ko, M.T., Total chromatic number and chromatic index of split graphs (1995) Journal of Combinatorial Mathematics and Combinatorial Computing, 17, pp. 137-146 Fiorini, S., Wilson, R.J., Edge-colourings of graphs (1977) Research Notes in Mathematics, , Pitman Holyer, I., The NP-completeness of edge-coloring (1981) SIAM Journal on Computing, 10, pp. 718-720 Ortiz, C., Maculan, N., Szwarcfiter, J.L., Characterizing and edge-colouring split-indifference graphs (1998) Discrete Applied Mathematics, 82, pp. 209-217 Plantholt, M., The chromatic index of graphs with a spanning star (1981) Journal of Graph Theory, 5, pp. 45-53 Vizing, V.G., On an estimate of the chromatic class of a p-graph (1964) Diskret. Analiz., 3, pp. 25-30