Novel Procedures for Graph Edge-colouring

• Leandro M. Zatesko UFPR
• Renato Carmo UFPR
• André L. P. Guedes UFPR

DOI: https://doi.org/10.5753/ctd.2019.6331

Resumo

We present a novel recolouring procedure for graph edge-colouring. We show that all graphs whose vertices have local degree sum not too large can be optimally edge-coloured in polynomial time. We also show that the set ofthe graphs satisfying this condition includes almost every graph (under the uniform distribution). We present further results on edge-colouring join graphs, chordal graphs, circular-arc graphs, and complementary prisms, whose proofs yield polynomial-time algorithms. Our results contribute towards settling the Over- full Conjecture, the main open conjecture on edge-colouring simple graphs. Fi- nally, we also present some results on total colouring.

Palavras-chave: Coloração de grafos e hipergrafos (MSC 05C15), Algoritmos de grafos (MSC 05C85), Teoria dos grafos em relação à Ciência da Computação (MSC 68R10), Graus de vértices (MSC 05C07), Operações de grafos (MSC 05C76).

Referências

Bodlaender, H. L. (1990). Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees. J. Algorithms, 11:631–641.

Cai, L. and Ellis, J. A. (1991). NP-completeness of edge-colouring some restricted graphs. Discrete Appl. Math., 30:15–27.

Chetwynd, A. G. and Hilton, A. J. W. (1984). The chromatic index of graphs of even order with many edges. J. Graph Theory, 8:463–470.

Chetwynd, A. G. and Hilton, A. J. W. (1986). Star multigraphs with three vertices of maximum degree. Math. Proc. Cambridge Philos. Soc., 100:303–317.

Chetwynd, A. G. and Hilton, A. J. W. (1989). 1-factorizing regular graphs of high degree: an improved bound. Discrete Math., 75:103–112.

Erd˝os, P. and Wilson, R. J. (1977). On the chromatic index of almost all graphs. J. Comb. Theory B, 23:255–257.

Erlebach, T. and Jansen, K. (2001). The complexity of path coloring and call scheduling. Theor. Comput. Sci., 255(1–2):33–50.

Figueiredo, C. M. H., Meidanis, J., and Mello, C. P. (1995). A greedy method for edge- colouring odd maximum degree double chordal graphs. Congr. Numer., 111:170–176.

Fournier, J.-C. (1977). Méthode et théorème générale de coloration des arêtes. J. Math. Pures Appl., 56:437–453.

Gandham, S., Dawande, M., and Prakash, R. (2005). Link scheduling in sensor networks: distributed edge coloring revisited. In Proc. 24th INFOCOM, pages 2492–2501.

Hilton, A. J. W. and Johnson, P. D. (1987). Graphs which are vertex-critical with respect to the edge-chromatic number. Math. Proc. Cambridge Philos. Soc., 102:103–112.

Holyer, I. (1981). The NP-completeness of edge-colouring. SIAMJ. Comput., 10(4):718– 720.

Koreas, D. P. (1997). The NP-completeness of chromatic index in triangle free graphs with maximum vertex of degree 3. J. Appl. Math. Comput., 93:13–17.

Machado, R. C. S., Figueiredo, C. M. H., and Vuškovi´c, K. (2010). Chromatic index of graphs with no cycle with a unique chord. Theor. Comput. Sci., 411:1221–1234.

Niessen, T. (1994). How to find overfull subgraphs in graphs with large maximum degree. Discrete Appl. Math., 51:117–125.

Ortiz Z., C., Maculan, N., and Szwarcfiter, J. L. (1998). Characterizing and edge- colouring split-indifference graphs. Discrete Appl. Math., 82:209–217.

Padberg, M. W. and Rao, M. R. (1982). Odd minimum cut-sets and b-matching. Math. Oper. Res., 7:67–80.

Vizing, V. G. (1964). On an estimate of the chromatic class of a p-graph (in Russian). Diskret. Analiz., 3:25–30.

Williamson, D. P., Hall, L. A., Hoogeveen, J. A., Hurkens, C. A. J., Lenstra, J. K., Sevast’janov, S. V., and Shmoys, D. B. (1997). Short shop schedules. Oper. Res., 45(2):288–294.