Novel procedures for graph edge-colouring

Abstract

The chromatic index of a graph G is the minimum number of colours needed to colour the edges of G in a manner that no two adjacent edges receive the same colour. By the celebrated Vizing’s Theorem, the chromatic index of any simple graph G is either its maximum degree ∆ or it is ∆+1, in which case G is said to be Class 1 or Class 2, respectively. Computing an optimal edge-colouring of a graph or simply determining its chromatic index are importantNP-hard problems which appear in noteworthy applications, like sensor networks, optical networks, production control, and games. In this work we present novel polynomial-time procedures for optimally edge-colouring graphs belonging to some large sets of graphs. For example, let X be the class of the graphs whose majors (vertices of degree ∆) have local degree sum at most ∆2−∆ (by ‘local degree sum’ of a vertex x we mean the sum of the degrees of the neighbours of x). We show that almost every graph is in X and, by extending the recolouring procedure used by Vizing’s in the proof for his theorem, we show that every graph in X is Class 1. We further achieve results in other graph classes, such as join graphs, circular-arc graphs, and complementary prisms. For instance, we show that a complementary prism can be Class 2 only if it is a regular graph distinct from the K2. Concerning join graphs, we show that if G1 and G2 are disjoint graphs such that |V(G1)|6|V(G2)|and ∆(G1) > ∆(G2), and if the majors of G1 induce an acyclic graph, thenthejoingraphG1∗G2 isClass1. Besidestheseresultsonedge-colouring,we present partial results on total colouring joingraphs,cobipartitegraphs,andcircular-arcgraphs, as well as a discussion on a recolouring procedure for total colouring.