Question on Regular Bipartite Graphs and Coloring

152 Views Asked by At

Here is a question I am stuck on: Let $G$ be a bipartite graph with partite sets $U$ and $W$ where $\Delta(G) = r \ge 1$ and $\delta(G) < r$. Show that if there is an $r$-regular bipartite graph $H$ containing $G$ as a subgraph such that at least one of the partite sets of $H$ is $U$ or $W$, then $\chi′(G) = \Delta(G)$. Here $\chi'(G)$ refers to the edge chromatic number for edge coloring.

Why should this even be true? enter image description here

Doesn't this contradict the claim? If not, is there any way I can prove this? If so, how? And finally, is there a bipartite graph with edge chromatic number greater than $\Delta(G)$?

Notation:

$\Delta(G)$ is max degree, $\delta(G)$ is min degree and partite sets refer to the two sets of vertices in bipartite graphs such that in each set, no two vertices are adjacent