### Some bound of the edge chromatic surplus of certain cubic graphs

#### Abstract

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.

#### Keywords

#### Full Text:

PDFDOI: http://dx.doi.org/10.5614/ejgta.2018.6.2.10

### Refbacks

- There are currently no refbacks.

ISSN: 2338-2287

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.