Novel Procedures for Graph Edge-colouring
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.
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.