Electronic Journal of Graph Theory and Applications 6 .
, 310Ae316 Some bound of the edge chromatic surplus of certain cubic graphs Diamantis Koreas Kapaneos 23.
Athens Greece dkoreas@gmail.
Abstract Vizing showed that any graph belongs to one of two classes: Class 1 if N0 (G) = OI(G) or in class 2 if N0 (G) = OI(G) 1, where N0 (G) and OI(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 .
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: edge coloring, edge critical graph Mathematics Subject Classification: 05C15 DOI: 10.
5614/ejgta.
Introduction An edge coloring of a graph is an assignment of AucolorsAy to the edges of the graph so that no two adjacent edges have the same color.
Such a coloring is said to be proper.
The edge-coloring problem asks whether it is possible to color properly the edges of a given graph with the fewest possible colors.
This paper is based on a previous work in .
, where the main problem in it is to Received: 26 September 2016.
Revised: 24 December 2017.
Accepted: 2 September 2018.
Some bound of the edge chromatic surplus of certain cubic graphs Diamantis Koreas find the chromatic surplus of the graph G, i.
, the minimum cardinality of colour classes over all edge-colourings of G.
In the present work the chromatic surplus of G is the minimum cardinality of the four color classes - over all 4-edge-colourings of G- and we set that this cardinality is held for the 4th color.
An upper bound of the chromatic surplus is given in .
in terms of two variables D and q.
Variable D denotes the distance between pairs of edges having color 4.
Variable q is related to the number of vertices that are endpoints of edges with color 4 and it is necessary to delete them, in order to get a 3-edge critical subgraph of G.
In the case that q = 0 and D > 3, this upper bound is near to the 0.
111 of the size of G Aujust a little bit betterAy than another well known upper bound .
1333 of the size of G) in .
But the case of q > 0 and D > 3 makes the difference, since then the upper bound in .
gets much better as q increases.
In other words, getting good upper bounds for the cardinality m depends on the values of the parameters q and D.
Computing or approximate the value of q is a difficult problem and therefore we try to find out restricted classes of cubic graphs with a structure that help us to evaluate it.
In the present paper, following the methods used in .
we study the class of non-planar cubic graphs in which in each pair of crossing edges the crossing edges are adjacent to a third edge.
Terminology, results and definitions we need We consider graphs without loops or multiple edges.
The girth of a graph is the length of a shortest cycle contained in the graph.
The chromatic index of a graph G is the minimum number of colors over all proper edge-coloring of G and it is denoted by N0 (G).
A graph is called 3-regular or cubic if all the vertices have degree 3.
Vizing proved that each graph belongs to one of the following two classes: Class 1 if N0 (G)=OI(G) or Class 2 if N0 (G)=OI(G) 1, where OI = OI(G) denotes the maximum degree of the graph G .
We shall call a graph edge-critical if it is connected, it is of class 2 and the removal of any edge transforms it to a graph of class 1.
In this paper when we say Aucritical graphAy we mean Auedge-critical graphAy.
If a critical graph has maximum degree OI, then we shall call it OI-critical.
Some basic results for a 3-edge critical graph G with n vertices are:
The number of vertices with degree 2 is at most n3 .
It does not contain adjacent vertices of degree 2.
For the proofs of these results see .
Definition 2.
The distance between two vertices u and v in a graph G, denoted by d.
, .
, is the length of a shortest path that connects them in G.
Definition 2.
The distance between two edges xy and uv is min.
, .
, d.
, .
, d.
, .
, d.
, .
In order to compute the minimum distance between more than two edges we have to check the distances for all possible pairs of edges.
For example if we want to compute the minimum distance between edges a, b and c we have to check the distances for the three pairs of edges .
, .
, .
, .
, .
and to find the minimum one.
Some bound of the edge chromatic surplus of certain cubic graphs Diamantis Koreas Definition 2.
A 4-edge coloring of G is said to be optimal if it minimizes the smallest cardinality m of color classes.
The main result We sketch in brief the ideas in .
Let a bridgeless cubic graph G of class 2 having an optimal 4-edge assignment.
Suppose that the AufourthAy color is assign to m edges.
If the m edges with the fourth color are deleted we will get a 3-edge colorable subgraph.
Let us delete only m Oe 1 of these edges.
We denote by v the mth edge that remains and by H the resulting subgraph of G.
Graph H is not 3-edge colorable, otherwise m is not a minimum.
First, we consider the case of H being critical.
We notice that the deletion of the m Oe 1 edges generates 2m Oe 2 vertices of degree 2.
Indeed it is impossible this deletion to generate less than 2m Oe 2 vertices of degree 2, because in that case two of the edges, which we have deleted, must be However, this is impossible since the deleted edges have been assigned the same fourth color in a proper 4-edge coloring of G.
From now on, we shall denote the set of the 2m Oe 2 vertices of degree 2 with M .
We have supposed that H is critical and therefore we get 2m Oe 2 O n3 or mO .
We assume now that H is not critical.
Note that H can be either connected or disconnected.
H consists of more than one components then only one of them is not 3-edge colorable, actually the one that has edge v.
So, in order to get a critical subgraph of H all the 3-edge colorable components must be deleted.
In both cases the deletion of some other edges except the edge v will give a subgraph of H that is critical, say H 0 of order n0 .
The deletion of other edges except the m Oe 1 ones that we first deleted it is possible to destroy some vertices of degree 2.
During the deletion of those edges a sequence of graphs H0 .
H1 , .
Hk O H 0 is generated.
Obviously in this sequence the first element is H and the last is H 0.
Suppose that a procedure decides in each step which edge .
r isolate vertex ) must be deleted in order to get finally a critical sub graph H 0 .
We examine the following cases:
Case 1.
In graph Hi there are no adjacent vertices of degree 2.
Suppose that the number 2m Oe 2 of vertices of degree 2 was reduced by one due to the deletion of an edge adjacent to a vertex of degree 2.
However, if we delete one edge adjacent to a vertex of degree 2 then we must also delete the other one as well because a 3-critical graph cannot have vertices of degree 1.
Therefore, the deletion of the second edge generates a vertex of degree 2.
So, at the end of this process two new vertices of degree 2 are generated.
Case 2.
In graph Hi there are adjacent vertices of degree 2.
We know that in a 3-critical graph there are no adjacent vertices of degree 2.
So, in order to get a critical graph these vertices must be deleted.
As we have seen in Case 1, the number 2m Oe 2 Some bound of the edge chromatic surplus of certain cubic graphs Diamantis Koreas cannot be reduced.
In this second case this number can be reduced.
This happens if we have adjacent vertices of degree 2.
Suppose that vertices a and b belong to M .
For a subgraph Hi vertices a and b can belong to a path of adjacent vertices of degree 2 for two reasons:
Edges ac and bd in which we have assigned color Au4Ay have distance 1, see Figure 1.
Then their deletion makes vertices a and b adjacent.
Edges ac and bd in which we have assigned color Au4Ay have distance greater than 1.
So, between them there are vertices of degree 3.
In these intermediate vertices are adjacent edges that have color that is not color Au4Ay.
If all these intermediate edges are deleted then we get a path of adjacent vertices of degree 2 to which vertices a and b belong.
In Figure 1 for example edges gh and ac are at distance 2.
With the deletion of the edge gh, vertex h has degree 2.
The deletion of vertex h does not reduce the initial number 2m Oe 2, due to generation of two vertices of degree 2 but if edge ij with color Au1Ay will be deleted then all the vertices in the path h Oe f becomes adjacent and the number 2m Oe 2 can be reduced with their deletion.
As we will see, if the previous reasons occur then the number 2m Oe 2 of vertices of degree 2 can be reduced.
At the same time the order n is also reduced.
If the number 2m Oe 2 is reduced by q and the order n by Q we will get the inequality:
mO 3q Oe Q Each step of the procedure that leads into a critical subgraph of G contributes an integer value to the expression 3q Oe Q .
hich sometimes we shall call simply 3q Oe Q).
For the rest of the paper we shall use 3q Oe Q in an informal way, meaning either its finally value .
hen we have reached the critical subgraph H 0 ) or meaning the value that it gets when we are working in a specific set of vertices, as a path or a circle.
For example, suppose that a vertex in M is deleted and its deletion generates two vertices of degree 2.
Then q = 1 Oe 2 = Oe1 and Q = 1, so 3q Oe Q = 3(Oe.
Oe 1 = Oe4.
Now, if one of these vertices of degree 2 is deleted and generates two other vertices of degree 2 then we have again 3q Oe Q = Oe4.
That means that these steps contribute to 3q Oe Q the integer value 3(Oe.
Oe 2 = Oe8 in total.
We examine when the expression 3q OeQ gets a maximum over all possible cases that can occur.
This maximum corresponds to the worst case that can occur and gives us an upper bound for m.
such upper bounds are studying and have as a basic parameter the distance D between vertices in M .
Unfortunately the upper bounds in .
that are much better that previously known upper bounds are valid only if we know in advance how many vertices of the initial 2m Oe 2 vertices of degree 2 will be delete by the procedure that leads into a critical subgraph of G.
So, we need the study of special types of cubic graphs that can ensure us that some of 2m Oe 2 vertices will be deleted.
In the present paper we will study the class of bridgeless and non-planar cubic graphs of girth at least 6, having minimum distance between crossing pairs D > 4 and for each of these pairs the crossing edges are at distance 1 apart.
Some bound of the edge chromatic surplus of certain cubic graphs Diamantis Koreas Figure 1.
Edges ac, bd and f e have color Au4Ay and are at distance 1.
If these edges are deleted then vertices a, b and f become adjacent.
Theorem 3.
Let G be a cubic bridgeless and non-planar cubic graph of girth g at least 6, with n vertices and l pairs of crossing edges with minimum distance D > 4 between pairs of crossing Suppose that in each pair of crossing edges the edges are at distance 1 apart.
If G belongs to Class 2 then for the chromatic surplus m of G the following inequality holds:
mO 1.
Proof.
We know from .
that if a bridgeless cubic graph belongs to class 2 then there is an optimal 4-edge coloring that uses color Au4Ay only into crossing edges and that at most half of the pairs of crossing edges is needed to get color Au4Ay.
Let a pair of crossing edges ab and cd having color Au4Ay and their endpoints b and d are adjacent, see Figure 2.
So, vertices b and d will belong to M .
Their deletion generates two new vertices of degree 2, say e, f .
Therefore, q = 2 Oe 2 = 0.
Q = 2 and 3q Oe Q = Oe2.
Vertices e and f cannot be adjacent because the girth of G is at least 6.
If these vertices are deleted then four vertices of degree 2 are generated, say g, h, i and j.
With the deletion of vertices e and f , 3q Oe Q gets the value 3 A .
Oe .
Oe 4 = Oe10.
Any further deletion of vertices gives a total value to 3q Oe Q less or equal to Oe2 because the deletion of the four new vertices of degree 2 contributes to 3q Oe Q a total value 3 A 2 Oe 8 = Oe2.
Notice that if the previous deleted vertices of degree 2 involve to another pair of crossing edges with color Au4Ay, i.
edges a0 b0 and c0 d0 then the total value of 3q Oe Q can be 3 A 4 Oe 12 = 0.
But this is impossible since D > 4.
The other endpoints a and c of the crossing edges ab and cd belong to M but are not adjacent, since g > 5.
Using the previous arguments we can assume that endpoints a and c will not be deleted, since their deletion will contribute in 3q Oe Q a negative value.
In other words, for the crossing edges ab and cd, the worst case occurs when the deleted vertices are only the endpoints b and d.
Some bound of the edge chromatic surplus of certain cubic graphs Diamantis Koreas Figure 2.
Edges ab and cd have color Au4Ay and their endpoints b and d are adjacent.
So, vertices b and d will belong to M .
Their deletion generates two vertices of degree 2, say e and f .
Therefore, q = 2 Oe 2 = 0.
If vertices e and f will be deleted then q = 2 Oe 2 2 Oe 4 = Oe2 due to generation of the four vertices of degree 2, say g, h, i and j.
Using the case where 3q Oe Q takes the value Oe2 and since at most 2l crossing pairs of edges are needed color Au4Ay after some calculations we get the desired inequality.
Indeed, let kl be the number of edges that must get color Au4Ay, where k O 12 .
So, m = kl.
Since in the worst case q = 0 or m O n6 .
61 ) Oe kl6 or m O n6 .
61 ) Oe m6 and and Q = kl we have: 2m Oe 2 O nOekl 1 finally m O 7 1.
Theorem 3.
Let G be a cubic bridgeless and non-planar cubic graph of girth g at least 6, with n vertices and l pairs of crossing edges with minimum distance D > 4 between pairs of crossing Suppose that in a A l pairs of crossing edges the edges are at distance 1 apart, where O a O 1.
If G belongs to class 2 then for the chromatic surplus m of G the following inequality n 2l.
Oe .
mO .
Proof.
Suppose that no all the pairs of crossing edges have their edges at distance 1 apart.
divide the set of the pairs of crossing edges into two disjoint subsets.
The first has all these pairs of crossing edges that have their edges at distance 1 and the second one has those pairs that have their edges at distance more than 1.
Suppose that graph G has l crossing pairs of edges but only a portion a of them belongs to the first subset.
So, a A l pairs belong to the first subset and .
Oe .
l pairs belong to the second one.
Let denote the first subset A and the second one B.
The proof follows for theorem 1 if we find out the number of pairs of crossing edges that belong to set A and required the color Au4Ay.
We know from .
that in an optimal 4-edge coloring of G color Au4Ay can be assigned only in crossing edges and that in every pair of crossing edges in which is assigned color Au4Ay AucorrespondsAy another pair of crossing edges in which one or two of the other colors Au1Ay.
Au2Ay, or Au3Ay are assigned.
The meaning of this AuconnectionAy is that there is another proper 4-edge coloring in which the assignment of the two pairs is reversed, i.
the second pair takes color Au4Ay and the first one takes the colors that the second one has.
Let kl be the number of edges that must get color Au4Ay, where k O 12 .
So, since kl2 pairs of crossing edges required color Au4Ay there are kl2 other pairs of crossing edges that alternate color Au4Ay Some bound of the edge chromatic surplus of certain cubic graphs Diamantis Koreas with the first kl2 pairs.
Suppose that kl > l.
Oe .
In that case we cannot cover all the crossing pairs having the color Au4Ay by crossing pair belonging only to B.
So, there exists a proper 4-edge coloring with at least kl2 Oe l.
Oe .
pairs of crossing edges that belong to A and get color Au4Ay.
The kl2 Oe l.
Oe .
pairs of crossing edges correspond to kl Oe 2l.
Oe .
edges and as in Theorem 1 we set q = 0 and Q = kl Oe 2l.
Oe .
After some calculation we get: 2m Oe 2 O nOem 2l.
Oe.
1 or m O n7 2l.
Oe.
Comments on the results We can find similar results as in Theorems 1 and 2 for other classes of G either by using different configurations where crossing edges are adjacent or by using different values for parameters D and g.
We also believe that is interesting the case where the adjacent crossing edges do not belong to the same crossing pair.
References