Some bound of the edge chromatic surplus of certain cubic graphs
Kapaneos 23, Athens Greece, Diamantis Koreas · Electronic Journal of Graph Theory and Applications · 2018
V.G. Vizing showed that any graph belongs to one of two classes: Class 1 if χ ʹ( G ) = Δ( G ) or in class 2 if χ ʹ( G ) = Δ( G ) + 1 , where χ ʹ( G ) and Δ( G ) denote the edge chromatic index of G and the maximum degree of G , respectively. This paper addresses the problem of finding the edge chromatic surplus of a cubic graph G in Class 2, namely the minimum cardinality of colour classes over all 4-edge chromatic colourings of E ( G ) . An approach to face this problem - using a new parameter q - is given in [1]. Computing q is difficult for the general case of graph G , so there is the need to find restricted classes of G , where q is easy to compute. Working in the same sense as in this paper we give an upper bound of the edge chromatic surplus for a special type of cubic graphs, that is the class of bridgeless non-planar cubic graphs in which in each pair of crossing edges, the crossing edges are adjacent to a third edge.