Artículos de revistas
On Edge-colouring Indifference Graphs
Registro en:
Theoretical Computer Science. , v. 181, n. 1, p. 91 - 106, 1997.
3043975
2-s2.0-0031189605
Autor
De Figueiredo C.M.H.
Meidanis J.
De Mello C.P.
Institución
Resumen
Vizing's theorem states that the chromatic index χ′(G) of a graph G is either the maximum degree Δ(G) or Δ(G) + 1. A graph G is called overfull if \E(G)| > Δ(G)[\V(G)|/2]. A sufficient condition for χ′(G) = Δ(G) + 1 is that G contains an overfull subgraph H with Δ(H) = Δ(G). Plantholt proved that this condition is necessary for graphs with a universal vertex. In this paper, we conjecture that, for indifference graphs, this is also true. As supporting evidence, we prove this conjecture for general graphs with three maximal cliques and with no universal vertex, and for indifference graphs with odd maximum degree. For the latter subclass, we prove that χ′ = Δ. 181 1 91 106 Cai, L., Ellis, J.A., NP-completeness of edge-colouring some restricted graphs (1991) Discrete Appl. Math., 30, pp. 15-27 De Figueiredo, C.M.H., Meidanis, J., De Mello, C.P., A greedy method for edge-colouring odd maximum degree doubly chordal graphs (1995) Congressus Numerantium, 111, pp. 170-176 De Figueiredo, C.M.H., Meidanis, J., De Mello, C.P., A lexbfs algorithm for proper interval graph recognition (1995) Inform. Process. Lett., 56, pp. 179-184 Hilton, A.J.W., Two conjectures on edge-colouring (1989) Discrete Math., 74, pp. 61-64 Hoffman, D.G., Rodger, C.A., The chromatic index of complete multipartite graphs (1992) J. Graph Theory, 16, pp. 159-163 Holyer, I., The NP-completeness of edge-coloring (1981) SIAM J. Comput., 10, pp. 718-720 Ortiz, C., (1994) Sobre Coloração de Arestas, , Ph.D. Thesis, COPPE-UFRJ, Rio de Janeiro, in portuguese Ortiz, C., Maculan, N., Szwarcfiter, J.L., (1996) Characterizing and Edge Colouring Split-indifference Graphs, , manuscript Padberg, M.W., Rao, M.R., Odd minimum cut-sets and b-matching (1982) Math. Oper. Res., 7, pp. 67-80 Plantholt, M., The chromatic index of graphs with a spanning star (1981) J. Graph Theory, 5, pp. 45-53 Plantholt, M., The chromatic index of graphs with large maximum degree (1983) Discrete Math., 47, pp. 91-96 Roberts, F.S., On the compatibility between a graph and a simple order (1971) J. Combin. Theory Ser. B, 11, pp. 28-38 Vizing, V.G., On an estimate of the chromatic class of a p-graph (1964) Diket. Analiz., 3, pp. 25-30. , in Russian