Decompositions For The Edge Colouring Of Reduced Indifference Graphs

dc.creatorDe Figueiredo C.M.H.
dc.creatorMeidanis J.
dc.creatorDe Mello C.P.
dc.creatorOrtiz C.
dc.date2003
dc.date2015-06-30T17:29:04Z
dc.date2015-11-26T15:41:00Z
dc.date2015-06-30T17:29:04Z
dc.date2015-11-26T15:41:00Z
dc.date.accessioned2018-03-28T22:49:29Z
dc.date.available2018-03-28T22:49:29Z
dc.identifier
dc.identifierTheoretical Computer Science. , v. 297, n. 01/03/15, p. 145 - 155, 2003.
dc.identifier3043975
dc.identifier10.1016/S0304-3975(02)00636-9
dc.identifierhttp://www.scopus.com/inward/record.url?eid=2-s2.0-0037282690&partnerID=40&md5=428418e878ad7b55482af6d8a1c8d911
dc.identifierhttp://www.repositorio.unicamp.br/handle/REPOSIP/102224
dc.identifierhttp://repositorio.unicamp.br/jspui/handle/REPOSIP/102224
dc.identifier2-s2.0-0037282690
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1264512
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. We present new positive evidence for the conjecture: every non neighbourhood-overfull indifference graph can be edge coloured with maximum degree colours. 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. We present two decomposition methods for edge colouring reduced indifference graphs with maximum degree colours. © 2002 Elsevier Science B.V. All rights reserved.
dc.description297
dc.description01/03/15
dc.description145
dc.description155
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., 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.descriptionDe Figueiredo, C.M.H., Meidanis, J., De Mello, C.P., Local conditions for edge-coloring (2000) J. Combin. Math. Combin. Comput., 32, pp. 79-91. , Tech. Rep., DCC 17/95, UNICAMP, 1995
dc.descriptionGutierrez, M., Oubiña, L., Minimum proper interval graphs (1995) Discrete Math., 142, pp. 77-85
dc.descriptionHammer, P.L., Peled, U.N., Sun, X., Difference graphs (1990) Discrete Appl. Math., 28, pp. 35-44
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 Anal., 3, pp. 25-30. , (in Russian)
dc.languageen
dc.publisher
dc.relationTheoretical Computer Science
dc.rightsfechado
dc.sourceScopus
dc.titleDecompositions For The Edge Colouring Of Reduced Indifference Graphs
dc.typeActas de congresos


Este ítem pertenece a la siguiente institución