# On Evenly-Equitable, Balanced Edge-Colorings and Related Notions

Authors: Aras Erzurumluoğlu; C. A. Rodger
Journal: International Journal of Combinatorics
 (2015)

---

## Abstract

A graphG is said to be even if all vertices of G have even degree. Given a k-edge-coloring of a graph G, for each color i∈Zk={0,1,…,k-1} let G(i) denote the spanning subgraph of G in which the edge-set contains precisely the edges colored i. A k-edge-coloring of G is said to be an even  k-edge-coloring if for each color i∈Zk, G(i) is an even graph. A k-edge-coloring of G is said to be evenly-equitable if for each color i∈Zk, G(i) is an even graph, and for each vertex v∈V(G) and for any pair of colors i,j∈Zk, |degG(i)(v)-degG(j)(v)|∈{0,2}. For any pair of vertices {v,w} let mG({v,w}) be the number of edges between v and w in G (we allow v=w, where {v,v} denotes a loop incident with v). A k-edge-coloring of G is said to be balanced if for all pairs of colors i and j and all pairs of vertices v and w (possibly v=w), |mG(i)({v,w})-mG(j)({v,w})|≤1. Hilton proved that each even graph has an evenly-equitable k-edge-coloring for each k∈N. In this paper we extend this result by finding a characterization for graphs that have an evenly-equitable, balanced k-edge-coloring for each k∈N. Correspondingly we find a characterization for even graphs to have an evenly-equitable, balanced 2-edge-coloring. Then we give an instance of how evenly-equitable, balanced edge-colorings can be used to determine if a certain fairness property of factorizations of some regular graphs is satisfied. Finally we indicate how different fairness notions on edge-colorings interact with each other.


---

## Body

## 1. Introduction

When considering edge-colorings of graphs it is usually desired to have some fairness properties imposed on the number of edges colored by each color. Below we define some important such notions and then explore the existence of edge-colorings satisfying combinations of these conditions.In what follows, a graphG is calledeven if all vertices of G have even degree. Given a k-edge-coloring of a graph G, for each color i∈Zk={0,1,…,k-1} let G(i) denote the spanning subgraph of G in which the edge-set contains precisely the edges colored i. Then a k-edge-coloring of G is called anevenk-edge-coloring if for each color i∈Zk, G(i) is an even graph. A k-edge-coloring of G is said to beequitable if for each vertex v∈V(G) and for each pair of colors i,j∈Zk, |deg⁡G(i)(v)-deg⁡G(j)(v)|∈{0,1}. Moreover, a k-edge-coloring of G is said to beevenly-equitableif(i)
for each colori∈Zk, G(i) is an even graph,(ii)
for each vertexv∈V(G) and for any pair of colors i,j∈Zk, |deg⁡G(i)(v)-deg⁡G(j)(v)|∈{0,2}.For any pair of vertices{v,w}, let mG({v,w}) be the number of edges between v and w in G (we allow v=w, where {v,v} denotes a loop incident with v). A k-edge-coloring of G is said to bebalanced if for all pairs of colors i and j and all pairs of vertices v and w (possibly v=w), |mG(i)({v,w})-mG(j)({v,w})|≤1. A k-edge-coloring of G is said to beequalized if EGi-EGj≤1 for each pair of colors i,j∈Zk.Due to de Werra’s work in [1–4] it has been known since the 1970s that for each k∈N every bipartite graph has a k-edge-coloring that is balanced, equitable, and equalized at the same time. One important result for more general graphs is by Hilton, who proved in [5] that each even graph has an evenly-equitable k-edge-coloring for each k∈N, thereby completely settling this problem (see Theorem 9). The existence of equitable k-edge-colorings is much more problematic and very unlikely to be completely solved, since, for example, settling the existence of equitable Δ-edge-colorings is equivalent to classifying Class 1 graphs (see [6, 7] for some results on this topic). One general result on equitable k-edge-colorings was found by Hilton and de Werra [8] who proved that if k≥2 and G is a simple graph such that no vertex in G has degree equal to a multiple of k, then G has an equitable k-edge-coloring. More recently, Zhang and Liu [9] extended this result by proving that for each k≥2, if the subgraph of G induced by the vertices which have degree equal to a multiple of k is a forest, then G has an equitable k-edge-coloring, thereby verifying a conjecture made by Hilton in [10].In Section2 we extend Hilton’s result [5] by finding a characterization for graphs that have an evenly-equitable, balanced k-edge-coloring for each k∈N (see Theorem 1). We then use this result to find a different kind of characterization for even graphs to have an evenly-equitable, balanced 2-edge-coloring (see Theorem 2).In Section3 we prove Theorems 5 and 6, the latter of which uses results from the previous section. The proof of Theorem 6 provides an instance of how evenly-equitable, balanced edge-colorings can be used to ensure that a certain fairness property of factorizations of some regular graphs is satisfied. This particular notion of fairness is defined as follows. A k-factorization of a graph in which the vertices have been partitioned into parts is said to be fair if for each two parts (possibly they are the same) the number of edges between these two parts in each factor differs from the number in each other factor by at most one.For completeness, in Section4 we address the existence of all other combinations of the three edge-coloring properties (namely, evenly-equitable, balanced, and equalized), finding weakest subsets of conditions that will guarantee (if possible) that a graph G has a k-edge-coloring which has the following properties in turn: (P1) evenly-equitable, balanced, and equalized, (P2) evenly-equitable and equalized, (P3) balanced and equalized, (P4) evenly-equitable, (P5) balanced, and (P6) equalized.For each proper subsetS of the vertex set of a graph G, define theedge-cutE(S,S¯)=e=x,y∣e∈EG,x∈S,y∈VG∖S. Let rG,k({v,w})∈Zk be such that rG,k({v,w})≡mG({v,w}) (modulo k). Let G(k) be the spanning subgraph of G in which for each pair of vertices v and w the number of edges between v and w is rG,k({v,w}). Then clearly deg⁡G(v)≡deg⁡G(k)(v) (modulo k) for all v∈V(G). For the purposes of this paper, a vertex v∈V(G(k)) is said to beodd (even) if (deg⁡G(v)-deg⁡G(k)(v))/k is an odd (even) integer.


## 2. Coloring Results

The following characterization can be used to find evenly-equitable, balancedk-edge-colorings. The proof has the flavor of Hilton’s proof in [5] of the case where the additional property of being balanced was not required but is modified to deal with extra complications that arise in this new setting.Theorem 1.
For each positive integerk, a graph G (possibly with loops) has an evenly-equitable, balanced k-edge-coloring if and only if it has an even, balanced k-edge-coloring.Proof.
Proving the “only if” result is trivial. To show the “if” result, we first prove the assertion for the case whenG is connected and loopless. Let f be an even, balanced k-edge-coloring of G. Among all pairs of colors i,j∈Zk and all vertices v∈V(G) suppose that |deg⁡G(i)(v)-deg⁡G(j)(v)|=2x is as large as possible (where x∈N). If x∈{0,1}, then this edge-coloring is evenly-equitable, so assume x≥2. Let G′ be the spanning subgraph of G induced by the edges colored i and j. From G′ form a new graph G′′ by adding an uncolored loop at each vertex v satisfying deg⁡G′(v)≡2 (mod 4). Then (1)deg⁡G′′(v)≡0mod⁡4foreachvertexv∈VG′′.For each pair of vertices {v,w} with v,w∈Zn and for any color h∈Zk, let mG(i,j)({v,w})=min⁡{mG(i)({v,w}),mG(j)({v,w})}, and let Si,j({v,w}) be a set of size 2mG(i,j)({v,w}) containing precisely mG(i,j)({v,w}) edges of each of the colors i and j joining vertices v and w. So |Si,j({v,w})| is even. Let Si,j(v)=⋃w∈V(G)∖{v}‍Si,j({v,w}) and Si,j=⋃0≤v<w<n‍Si,j({v,w}). Define G′′′=G′′-Si,j. Since |Si,j(v)| is even for each v∈V(G), and since the original edge-coloring is even, each component of G′′′ is an eulerian graph and has no multiple edges since f is balanced (possibly it has an uncolored loop at some of the vertices). The following argument establishes property (4); namely, each component of G′′′ has an even number of edges. First note that by the assumption of this theorem for all h∈Zk each component of G(h) is eulerian, so (2)thesizeofeachedge-cutinG(h)isevensoitisalsoeveninG′′h.Let C be any component of G′′′ and let H=G[Si,j]. Let E1=E(H[V(C)]); so |E1| is even (since there are an even number of edges in Si,j between each pair of vertices). Let E2 be the edge-cut H[V(C),V(H)∖V(C)], which by the definition of Si,j satisfies H[V(C),V(G)∖V(C)]=G′′[V(C),V(G)∖V(C)]. So, |E2∩E(H(i))|=|E2∩E(H(j))|. Furthermore, since for each color h∈{i,j}E2∩E(H(i)) and E2∩E(H(j)) are edge-cuts in H(i) and H(j), respectively, by (2)  |E2∩E(H(i))| and |E2∩E(H(j))| are even. Hence |E2|=|E2∩E(H(i))|+|E2∩E(H(j))|=2|E2∩E(H(i))|≡0 (mod 4). Then,(3)∑v∈VC‍deg⁡G′′′v=∑v∈VC‍deg⁡G′′(v)-2E1-E2≡∑v∈VC‍deg⁡G′′v(mod⁡4)≡0(mod⁡4)by(1).
So,(4)EC=∑v∈VCdeg⁡G′′′v2≡0(mod⁡2).
Letf′ be a new 2-edge-coloring of G′ formed as follows. For each component C of G′′′, alternately color the edges of an eulerian circuit of C with i and j. This yields a balanced 2-edge-coloring of G′′′ (G′′′ is simple) where by (4), for each vertex v∈V(G), (5)deg⁡G′′′iv=deg⁡G′′′jv.
Now add the edges inSi,j with their original colors to G′′′ and remove the uncolored loops that were added when forming G′′. Then clearly the resulting graph is G′ and this new 2-edge-coloring f′ satisfies |deg⁡G′(i)(v)-deg⁡G′(j)(v)|∈{0,2} for each v∈VG′. To show that f′ is also even, consider the following cases (in which deg⁡G′′′(i)(v) refers to edge-coloring G′′′ with f′).
Case 1. One has deg⁡G′(v)≡0 (mod 4). Note that in this case we are not adding a loop at v when forming G′′. Now look at the following subcases.
Subcase 1.1. ∑w∈V(G′)∖{v}‍mG(i,j)({v,w}) is odd. So, an odd number of edges incident with v of each of the colors i and j were removed when forming G′′′ from G′′. So, deg⁡G′′′(v)≡2 (mod 4) and hence by (5)  deg⁡G′′′(i)(v)≡deg⁡G′′′(j)(v)≡1 (mod 2). Putting back the removed edges shows that v is incident with an even number of edges of each color in the edge-coloring f′ of G′.
Subcase 1.2. ∑w∈V(G′)∖{v}‍mG(i,j)({v,w}) is even. So, an even number of edges incident with v of each of the colors i and j were removed when forming G′′′. So, deg⁡G′′′(v)≡0 (mod 4) and hence deg⁡G′′′(i)(v)≡deg⁡G′′′(j)(v)≡0 (mod 2). Putting back the removed edges shows that v is incident with an even number of edges of each color in the edge-coloring f′ of G′.
Case 2. One has deg⁡G′(v)≡2 (mod 4). Note that in this case an uncolored loop is added to v when forming G′′. Now look at the following subcases.
Subcase 2.1. ∑w∈V(G′)∖{v}‍mG(i,j)({v,w}) is odd. So, after adding an uncolored loop at v, an odd number of edges incident with v of each of the colors i and j were removed when forming G′′′. Then deg⁡G′′′(v)≡2 (mod 4), so by (5) in the new edge-coloring deg⁡G′′′(v)=deg⁡G′′′(w)≡1 (mod 2). So, for each u∈{v,w} and each l∈i,j,deg⁡G′(l)(u)=deg⁡G′′′(l)(u)+mG(i,j)({v,w})≡0 (mod 2).
Subcase 2.2. ∑w∈V(G′)∖{v}‍mG(i,j)({v,w}) is even. So, after adding an uncolored loop at v, an even number of edges incident with v of each of the colors i and j were removed when forming G′′′. Then deg⁡G′′′(v)≡0 (mod 4), so by (5) in the new edge-coloring deg⁡G′′′(v)=deg⁡G′′′(w)≡0 (mod 2). So, for each u∈{v,w} and each l∈i,j, deg⁡G′(l)(u)=deg⁡G′′′(l)(u)+mG(i,j)({v,w})≡0 (mod 2).
Repetition of this procedure yields an evenly-equitable, balancedk-edge-coloring of G.
For the case whenG has loops and is possibly disconnected, simply remove all the loops from G and apply this procedure to each component of the resulting loopless graph to get an evenly-equitable, balanced k-edge-coloring of each component. Then put back the loops; it is easy to color them in a balanced way without destroying the evenly-equitable property at each vertex.Note that in the statement of Theorem1 we cannot replace the condition on the existence of an even, balanced k-edge-coloring by a weaker set of conditions, as is illustrated by the next two examples. A cycle of length 3 with a cycle of length 2 intersecting in one of its vertices is an even graph and clearly has a balanced (and equalized) 2-edge-coloring, but no 2-edge-coloring that is evenly-equitable and balanced. The graph 2K2 (the graph with two vertices and two edges joining these two vertices) has an even (actually evenly-equitable) 2-edge-coloring, but no 2-edge-coloring that is evenly-equitable and balanced. While these two graphs are trivial, they can be generalized to more complicated examples.Theorem1 leads to the problem of finding conditions guaranteeing that a graph has an even, balanced k-edge-coloring. The following result addresses that problem. Recall that our unusual definitions of even and odd vertices and of G(2) are given at the end of Section 1.Theorem 2.
G has an even, balanced 2-edge-coloring if and only if G is even and G(2) has no components with an odd number of odd vertices.Proof.
To prove the necessity, suppose that an even, balanced2-edge-coloring of G is given. Since the given 2-edge-coloring is balanced, for each pair of vertices v and w, the mG({v,w})-rG,2({v,w}) edges between v and w that are to be deleted when forming G(2) from G can be chosen so that they are shared evenly among the two color classes. Let C be a component in G(2). Now since the given 2-edge-coloring of G is even, for each color i∈Z2, an odd vertex in C contributes an odd number to the degree sum of the graph G(2)(i), and an even vertex in C contributes an even number to the degree sum of the graph G(2)(i). Hence the number of odd vertices in C must be even.
To show the sufficiency, color the edges inG as follows. To satisfy the balanced property, for each pair of vertices {v,w}⊆V(G) color (mG({v,w})-rG,2({v,w}))/2 (note that by definition of rG,2 this is an integer) of the edges between v and w with each color i∈Z2. Let G∗ be the graph induced by the edges that have been colored so far, and note that the graph induced by the uncolored edges is G(2). Also note that by the definition of odd and even vertices, for each i∈Z2, ∗deg⁡G∗(i)(v)isodd(even)ifandonlyifvisanodd(even)vertex.Since G is an even graph and since mG({v,w})-rG,2({v,w}) is even for each {v,w}⊆V(G), G(2) is also an even graph. For each component C in G(2) color the edges of an eulerian tour of C as follows. Start by coloring the first edge in the eulerian tour with i∈Z2 and then switch to i+1 (modulo 2) whenever the eulerian tour reaches an odd vertex for the first time. Note that if the first vertex in the eulerian tour is even, then the first and last edges in the eulerian tour will have the same color because an even number of color switches will occur (by assumption there are an even number of odd vertices). Similarly, if the first vertex, say v, is odd, then the first and the last edges will have different colors if deg⁡G(2)(v)=2 (since no color switch is made at v) and they will have the same color if deg⁡G(2)(v)>2 (since then the eulerian tour will pass through v, so a color switch will occur at v). This coloring of the edges in G(2) has the property that for each v∈V(G) and for each i∈Z2(i)
ifv is odd, then deg⁡G(2)(i)(v) is odd,(ii)
ifv is even, then deg⁡G(2)(i)(v) is even. So, for each i∈Z2 and each v∈V(G), since deg⁡G(i)(v)=deg⁡G(2)(i)(v)+deg⁡G∗(i)(v), by ∗, (i), and (ii) each vertex in G(i) has even degree and hence the given 2-edge-coloring has the desired properties.It appears to us that a generalization of Theorem2 for three or more colors may be difficult to obtain.The following result characterizes graphs which have an evenly-equitable, balanced2-edge-coloring.Corollary 3.
Suppose thatG is an even graph. Then G has an evenly-equitable, balanced 2-edge-coloring if and only if G(2) has no components with an odd number of odd vertices.Proof.
This follows immediately by Theorems1 and 2.


## 3. An Application Using Amalgamations

In this section edge-colorings that satisfy another notion of equally distributing edges across color classes are considered, namely, that of fairness. Not only are the edge-colorings equitable, but also for any given partitionP of the vertices, for each two parts in P (possibly they are the same) the edges between vertices in the two parts are equally divided among the color classes. While the results here (Theorems 5 and 6) address general partitions, these types of questions naturally arise when edge-coloring the complete multipartite graph Ka1,...,ap, in which the partition is chosen to be the parts of the graph. For example, it has been shown when there exist fair equitable edge-colorings of Ka1,…,ap in which each color class induces a hamilton cycle [11] or a 1-factor [12].To prove Theorem5, the method of amalgamations is used. A graph H is said to be the ψ-amalgamation of a graph G if ψ is a function from V(G) onto V(H) such that e={u,v}∈E(G) if and only if {ψ(u),ψ(v)}∈E(H). The function ψ is called an amalgamation function. We say that G is adetachment of H, where each vertex v of H splits into the vertices of ψ-1({v}). An η-detachment of H is a detachment in which each vertex v of H splits into η(v) vertices. Amalgamating a finite graph G to form the corresponding amalgamated graph H can be thought of as grouping the vertices of G and forming one supervertex for each such group by squashing together the original vertices in the same group. An edge incident with a vertex in G is then incident with the corresponding new vertex in H; in particular an edge joining two vertices from the same group becomes a loop on the corresponding new vertex in H.In what follows,G[j] denotes the subgraph of G induced by the edges colored j (so unlike G(j), G[j] is not necessarily a spanning subgraph), and lG(u) denotes the number of loops at u in G. The following theorem was proved in much more generality by Bahmanian and Rodger in [13], but this is sufficient for our purposes.Theorem 4.
LetH be a k-edge-colored graph and let η be a function from V(H) into N such that for each w∈V(H), η(w)=1 implies lH(w)=0. Then there exists a loopless η-detachment G of H with amalgamation function ψ:V(G)→V(H), η being the number function associated with ψ, such that G satisfies the following property: (i)
deg⁡G[j](u)∈{deg⁡H[j](w)/η(w),deg⁡H[j](w)/η(w)} for each w∈V(H) and each u∈ψ-1(w) and each j∈Zk,(ii)
mG(u,u′)∈{lH(w)/(η(w)(η(w)-1)/2),lH(w)/(η(w)(η(w)-1)/2)} for each w∈V(H) with η(w)≥2 and every pair of distinct vertices u,u′∈ψ-1(w),(iii)
mG(u,v)∈{mH(w,z)/(η(w)η(z)), mH(w,z)/(η(w)η(z))} for every pair of distinct vertices w,z∈V(H), each u∈ψ-1(w), and each v∈ψ-1(z).The following theorem provides a necessary condition for the existence of fair 2-factorizations of4k-regular graphs (k≥1). For any graph G and any partition P of V(G), let P(G) be the ψ-amalgamation of G, where ψ maps two vertices in G to the same vertex in P(G) if and only if they are in the same element of P.Theorem 5.
LetG be a 4k-regular graph (k≥1). Let P be any partition of V(G). Let H=P(G). Suppose that G has a fair 2k-factorization. Then (1)
H(2) has no components with an odd number of odd vertices.Proof.
Suppose thatG has a fair 2k-factorization. Let F1 and F2 be the subgraphs of H induced by the edges corresponding to the 2k-factors of G. Since at each vertex in H the number of edge-ends incident with a vertex is a multiple of 4 and since these edge-ends are shared evenly among F1 and F2, the number of edge-ends incident with each vertex in H in each of F1 and F2 is even. So, by the definition of odd and even vertices, in H(2) an odd vertex is incident with an odd number of edge-ends in each of F1 and F2, and an even vertex is incident with an even number of edge-ends in each of F1 and F2. Let C be a component of H(2). Clearly ∑v∈V(C)‍deg⁡C(v) is an even number and (6)∑v∈VC‍deg⁡Cv=∑v∈VCisodd‍deg⁡C(v)+∑v∈V(C)iseven‍deg⁡C(v),where ∑v∈V(C)iseven‍deg⁡C(v) is an even number and each term in the summation ∑v∈V(C)isodd‍deg⁡C(v) is an odd number by the above observation. Hence the number of odd vertices in V(C) must be even.To investigate whether the necessary condition given in Theorem5 is also sufficient for a graph to have a fair 2k-factorization, we introduce the notion of P-equivalence.LetG1 and G2 be two graphs with V(G1)=V(G2)=V, and let P be a partition of V. Then G1 is said to be P-equivalent to G2 if for all Vi,Vj∈P (possibly i=j) e(G1(Vi,Vj))=e(G2(Vi,Vj)), where e(Gk(Vi,Vj)) denotes the number of edges in Gk (for k=1,2) between the parts Vi and Vj. So if G1 and G2 are P-equivalent, then H=P(G1)=P(G2). If either G1 or G2 has a fair 2k-factorization, then Theorem 5 shows that (1) must be satisfied. To investigate the strength of (1), Theorem 6 shows that if G is a 4-regular graph for which H(2)=P(G)(2) satisfies (1), then G is P-equivalent to some graph (which is simple if a certain necessary condition is met) with a fair 2-factorization. Conjecture 7 goes on to make a much stronger claim that if G1 is P-equivalent to G2, then G1 has a fair 2k-factorization if and only if G2 does.Theorem 6.
LetG1 be a 4-regular graph. Let P be any partition of V(G1). Let H=P(G1). Suppose H(2) has no components with an odd number of odd vertices. Then there exists a graph G2 such that(i)
V(G1)=V(G2),(ii)
G2 is P-equivalent to G1,(iii)
G2 has a fair 2-factorization (with respect to the given partition P),(iv)
G2 can be chosen to be simple if and only if for all Vi,Vj∈P, e(Vi,Vj)≤ViVj if i≠j, and e(Vi,Vj)≤Vi(Vi-1)/2 if i=j.Note that it is long known by Petersen’s2-factor theorem (see, e.g., [14]) that every 2k-regular graph has a 2-factorization. The importance of Theorem 6 is that if the condition of the theorem is satisfied, then regardless of the partition P that is chosen, the resulting factorization of G2 (formed with P in mind) is fair.Proof.
By the suppositionH(2) has no components with an odd number of odd vertices. Clearly H is even since G1 is even. So H satisfies the conditions of Corollary 3 and hence it has an evenly-equitable, balanced 2-edge-coloring. By the evenly-equitable property of this 2-edge-coloring, each color appears on exactly half of the edge-ends incident with each vertex of H (a loop contributes two edge-ends to the incident vertex). Notice that H is the ψ-amalgamation of G1 where ψ(v1)=ψ(v2) if and only if v1 and v2 are in the same element of P. For each v∈V(H) define η(v)=deg⁡H(v)/4=|ψ-1(v)|. By (i) of Theorem 4, there exists an η-detachment G2 of H such that (1)
G2 is P-equivalent to G1,(2)
for each vertexv of H the edges of each color incident with v are shared as evenly as possible among the vertices in ψ-1(v) (i.e., the vertices in the corresponding part of G2). Note that, by (ii) and (iii) of Theorem 4, G2 will be simple if for all Vi,Vj∈P, e(Vi,Vj)≤|Vi||Vj| if i≠j, and e(Vi,Vj)≤|Vi|(|Vi|-1)/2 if i=j. Clearly these are necessary conditions if the η-detachment of H is to be simple.
By (2), in G2 each color is on two edges incident with each vertex. So, in G2 the subgraph induced by the edges of each color is a 2-factor, and hence this 2-edge-coloring is a 2-factorization of G2. The fairness of this 2-factorization follows from the following observation: There is a one-to-one correspondence between the edges colored c joining any pair of vertices u and w in H and the edges colored c between the two corresponding parts ψ-1(u) and ψ-1(w) of G2. So, the balanced property of this 2-edge-coloring implies the required fairness property of the 2-factorization.In the light of Theorems5 and 6 we make the following conjecture.Conjecture 7.
LetG be a 4k-regular graph (k≥1). Let P be any partition of V(G). Let H=P(G). Suppose H(2) has no components with an odd number of odd vertices. Then G has a fair 2k-factorization.


## 4. Other Combinations of Requirements

As described in the introduction we now consider other combinations of edge-coloring properties in turn. The results in this section are straight forward to obtain but are reported here for completeness.(P1) Evenly-equitable, balanced, and equalized: as is discussed below, the examples in Figure 1 show that there are graphs which have an even, balanced, equalized 2-edge-coloring, but no 2-edge-coloring that is evenly-equitable and equalized. So, for each positive integer k, no matter which combination of the conditions on the existence of an even k-edge-coloring, balanced k-edge-coloring and equalized k-edge-coloring of a graph G is used, it is not possible to guarantee that G has a k-edge-coloring which is evenly-equitable, balanced, and equalized.Figure 1
Examples of graphs that are not of color-type 1.
(a)
G
1: A vertex-minimum example
(b)
G
2: An edge-minimum exampleA graph is said to be ofcolor-type1 if it is connected and simple and has an even, equalized 2-edge-coloring but has no evenly-equitable, equalized 2-edge-coloring. Note that any edge-coloring of a color-type 1 graph is balanced because it is simple. In G1 there are two 3-cycles that intersect in just the top vertex; color the six edges in these 3-cycles with color 0 and color the remaining edges with color 1 to produce an even, balanced, equalized 2-edge-coloring. G1 does not have an evenly-equitable, equalized 2-edge-coloring, since in every evenly-equitable 2-edge-coloring one color class must be 2-regular and spanning and so has 7 edges. So, G1 is of color-type 1. In fact, a basic search shows that there is no color-type 1 graph with fewer vertices nor one on 7 vertices with less than 12 edges.InG2 the six edges of the two 3-cycles can be colored with color 0 and the edges of the 5-cycle with color 1, thereby producing an even, balanced, equalized 2-edge-coloring. G2 does not have an evenly-equitable, equalized 2-edge-coloring, since the only evenly-equitable 2-edge-coloring has one color class consisting of the three edges in the middle 3-cycle. So, G2 is of color-type 1. In fact, another basic search shows that there is no color-type 1 graph with fewer edges nor one with 11 edges on less than 9 vertices.Note thatG2 suggests a way to construct infinitely many color-type 1 graphs: Take any cycle of length a as the middle cycle, attach to it a cycle of length b on the left and a cycle of length c on the right where c∈{a+b-1,a+b,a+b+1}, and a,b,c≥3.Since we cannot guarantee the existence of an evenly-equitable, balanced, and equalizedk-edge-coloring of a graph G, even with the strong assumption that G has a k-edge-coloring which is even, balanced, and equalized, we focus our attention on conditions implying the existence of k-edge-colorings that are (P2) evenly-equitable and equalized, (P3) balanced and equalized, (P4) evenly-equitable, (P5) balanced, and (P6) equalized; evenly-equitable, balanced edge-colorings are the focus of Section 2.(P2) Evenly-equitable and equalized: the examples in Figure 1 show that even with the strong assumption that a graph G has an even, balanced, equalized k-edge-coloring, G does not necessarily have an evenly-equitable, equalized k-edge-coloring; characterizations of graphs with such edge-colorings would seem to be difficult to find.(P3) Balanced and equalized: such edge-colorings are always easy to find as is stated in the following theorem.Theorem 8.
For each positive integerk, each graph has a balanced, equalized k-edge-coloring.Proof.
LetG be a graph with m edges (loops, being special types of edges, are also included in this count). Form an ordering (e1,e2,…,em) of the edges of G where loops incident with the same vertex appear consecutively in the list, as do the edges joining the same pair of vertices. For 1≤i≤m color ei with i (modulo k). This k-edge-coloring is clearly balanced and equalized.(P4) Evenly-equitable: Hilton proved the following theorem in [5].Theorem 9.
For eachk≥1, each even graph G has an evenly-equitable k-edge-coloring.Note that the condition thatG is even is clearly necessary.(P5) Balanced: by Theorem 8 for each positive integer k, any graph G has a balanced k-edge-coloring.(P6) Equalized: by Theorem 8 for each positive integer k, any graph G has an equalized k-edge-coloring.The discussion above leads to the chart in Table1.Table 1
G has an even, balanced, equalized k-edge-coloring for each positive integer k
⇏  by (P1)
G has an evenly-equitable, equalized k-edge-coloring for each positive integer k
G has an even, balanced k-edge-coloring for each positive integer k
⇔  by Theorem 1
G has an evenly-equitable, balanced k-edge-coloring for each positive integer k
G is any graph
⇒  by Theorem 8
G has a balanced, equalized k-edge-coloring for each positive integer k
G is even
⇒  by Theorem 9
G has an evenly-equitable k-edge-coloring for each positive integer k



---

*Source: 201427-2015-03-04.xml*