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

Abstract

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.

Keywords: Colouring of graphs and hypergraphs (MSC 05C15), Graph algorithms (MSC 05C85), Graph theory in relation to Computer Science (MSC 68R10), Vertex degrees (MSC 05C07), Graph operations (MSC 05C76).

References

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.