### Mixed graph edge coloring

##### Source Information
June 2009, Volume309(Issue12) Page4027To4036

Appendix A proof of Theorem 4.2

Proof

Consider the relevant (2, 3)-regular bipartite graph $G M$ constructed in the proof of Theorem 4.1 . Observe that all its degree 2 vertices are in the same partition, and the number of these vertices is divisible by three. Now, let $G M ∗ = ( V ∗ , U ∗ , E ∗ )$ be the graph resulting from connecting all the triples of degree 2 vertices in $G M$ with the gadget depicted in Fig. 6 (triples are chosen in an arbitrary manner). By the construction, $G M ∗$ is cubic and bipartite, with $l ( G M ∗ ) = 3$ and $E ∗ = 0̸$ . And, taking into account the proof of Theorem 4.1 and the fact that $G M$ is a subgraph of $G M ∗$ , all we need is to prove that 5-colorability of $G M$ implies 5-colorability of $G M ∗$ .

Consider a vertex $v$ of degree 2 in $G M$ . Observe that in any 5-coloring of $G M$ , none of the arcs incident to $v$ is assigned color 1. This follows from the fact that $i n ( v ) = 2$ , and that the outer degree of $v$ is 1 in $G M$ . Next, consider again the gadget in Fig. 6 . It is 4-colorable in a manner that the arcs incident to vertices $x , y$ , and $z$ are assigned color 1 (one of such colorings is depicted in the figure). Consequently, bearing in mind the aforementioned observation for any 5-coloring of edges incident to a degree 2 vertex in $G M$ , one can easily extend edge 5-coloring of $G M$ onto arcs of $G M ∗$ : all arcs of $G M ∗$ that are present in $G M$ are just colored as in $G M$ , and all the other arcs are colored in the manner depicted in Fig. 6 . And thus, edge 5-colorability of $G M$ implies edge 5-colorability of $G M ∗$ .□

##### Keywords

doi: 10.1016/j.disc.2008.11.033