Edge Colouring Reduced Indifference Graphs

dc.creatorDe Figueiredo C.M.H.
dc.creatorDe Mello C.P.
dc.creatorOrtiz C.
dc.date2000
dc.date2015-06-30T19:49:11Z
dc.date2015-11-26T14:46:37Z
dc.date2015-06-30T19:49:11Z
dc.date2015-11-26T14:46:37Z
dc.date.accessioned2018-03-28T21:56:28Z
dc.date.available2018-03-28T21:56:28Z
dc.identifier3540673067; 9783540673064
dc.identifierLecture Notes In Computer Science (including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics). , v. 1776 LNCS, n. , p. 145 - 153, 2000.
dc.identifier3029743
dc.identifier10.1007/10719839_16
dc.identifierhttp://www.scopus.com/inward/record.url?eid=2-s2.0-84896783019&partnerID=40&md5=a4d61589928cbffddcfd996f21c9439c
dc.identifierhttp://www.repositorio.unicamp.br/handle/REPOSIP/107081
dc.identifierhttp://repositorio.unicamp.br/jspui/handle/REPOSIP/107081
dc.identifier2-s2.0-84896783019
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1252921
dc.descriptionThe 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. 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. © Springer-Verlag Berlin Heidelberg 2000.
dc.description1776 LNCS
dc.description
dc.description145
dc.description153
dc.descriptionCai, L., Ellis, J.A., NP-completeness of edge-colouring some restricted graphs (1991) Discrete Appl. Math., 30, pp. 15-27
dc.descriptionDe Figueiredo, C.M.H., Meidanis, J., De Mello, C.P., A linear-time algorithm for proper interval graph recognition (1995) Inform. Process. Lett., 56, pp. 179-184
dc.descriptionDe Figueiredo, C.M.H., Meidanis, J., De Mello, C.P., Local conditions for edge-coloring (1995) J. Combin. Mathematics and Combin. Computing, 31. , Technical report, DCC 17/95, UNICAMP To appear
dc.descriptionDe Figueiredo, C.M.H., Meidanis, J., De Mello, C.P., On edge-colouring indifference graphs (1997) Theoret. Comput. Sci., 181, pp. 91-106
dc.descriptionDe Figueiredo, C.M.H., Meidanis, J., De Mello, C.P., Total-chromatic number and chromatic index of dually chordal graphs (1999) Inform. Process. Lett., 70, pp. 147-152
dc.descriptionGutierrez, M., Oubinã, L., Minimum proper interval graphs (1995) Discrete Math., 142, pp. 77-85
dc.descriptionHedman, B., Clique graphs of time graphs (1984) J. Combin. Theory Ser. B, 37, pp. 270-278
dc.descriptionHilton, A.J.W., Two conjectures on edge-colouring (1989) Discrete Math., 74, pp. 61-64
dc.descriptionHolyer, I., The NP-completeness of edge-coloring (1981) SIAM J. Comput., 10, pp. 718-720
dc.descriptionMisra, J., Gries, D., A constructive proof of vizing's theorem (1992) Inform. Process. Lett., 41, pp. 131-133
dc.descriptionRoberts, F.S., On the compatibility between a graph and a simple order (1971) J. Combin. Theory Ser. B, 11, pp. 28-38
dc.descriptionVizing, V.G., On an estimate of the chromatic class of a p-graph (1964) Diskrete Analiz., 3, pp. 25-30. , In Russian
dc.languageen
dc.publisher
dc.relationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
dc.rightsfechado
dc.sourceScopus
dc.titleEdge Colouring Reduced Indifference Graphs
dc.typeActas de congresos


Este ítem pertenece a la siguiente institución