13
$\begingroup$

A theorem of König says that

Any bipartite graph $G$ has an edge-coloring with $\Delta(G)$ (maximal degree) colors.

This document proves it on page 4 by:

  1. Proving the theorem for regular bipartite graphs;
  2. Claiming that if $G$ bipartite, but not $\Delta(G)$-regular, we can add edges to get a $\Delta(G)$-regular bipartite graph.

However, there seem to be two problems with the second point:

  • A regular bipartite graph has the same number of vertices in the two partions. So we need to add vertices also.
  • I'm not sure that it is always possible to add edges to get a $\Delta$-regular bipartite graph, even if we have the same number of vertices. See the figure below. B and E both have degree two, but we cannot make them degree 3

Am I right ? Is there a way to correct that ?

$\endgroup$
  • 1
    $\begingroup$ A good way to do this is to prove that any bipartite graph has a matching that covers each vertex of maximum degree. (The proof of this is got using the ideas you'd use to prove Koenig's theorem. It's not trivial.) As your example shows, you cannot always make a bipartite graph regular by adding edges. $\endgroup$ – Chris Godsil Jul 2 '12 at 14:04
  • 3
    $\begingroup$ Is there is any problem with having multiple edges in this proof? If not you can just add another edge between E and B. Similarly, it is possible to add isolated vertices to the graph (to get the same number of vertices in each set) before adding the edges and the colouring of the regular graph thus formed will transfer back to the original graph. $\endgroup$ – jp26 Jul 2 '12 at 14:07
  • 1
    $\begingroup$ The document you quote starts off by saying "We assume in this chapter that $G$ has no loops." Evidently, the discussion is not restricted to simple graphs, multiple edges are allowed. There is no good reason to restrict the discussion to simple graphs; the theorem is true for graphs with multiple edges, and restricting it to simple graphs does not make the proof easier. Of course you still have to add vertices to get the same number of vertices on both sides. $\endgroup$ – bof Oct 26 '14 at 0:28
  • $\begingroup$ I second bof's comment at 'Oct 26 '14 at 0:28': Frieze's proof(-sketch) is correct, because 'graph' means 'multigraph' in the document in question. $\endgroup$ – Peter Heinig Feb 27 '18 at 7:03
3
$\begingroup$

You have to be allowed to add vertices. In that case it is provable by induction on the number of edges:
Assume G' := G \ e is a Subgraph of some Δ'-regular bipartite Graph K'.
1. Case Δ = Δ' + 1:
K = K' plus e plus an edge for every two other vertices.
2. Case e is in K':
K = K'
3. Case e is not in K':
Let e = (a,b). Because we do not increase Δ, there must be edges in K' \ G' f = (a,c) and g = (b,d). Make a copy of K' =: K'' and join them. Remove f, g and their copies. Connect e, the copy of e, (a,c'), (b,d'), (a',c), (b',d). Here a' is the copy of a etc.. This gives K with all the right edges and degrees.

We can start the induction at 0 edges, and take as K an edgeless bipartite Graph with partitions of the same size, so that it includes G.

Case 3 can done sometimes without the doubling of the graph, but not always. Your example is a case, which can be solved by doubling the graph. Adding vertices is also no problem for your point 1, because it is independent of the number of vertices.

$\endgroup$
  • $\begingroup$ in the 3rd case if you add both e and (a,c') the degree of a will increase. Probably you need to add only (b,d') and (b',d) .. Do I get it right? $\endgroup$ – Hrant Khachatrian Apr 17 '15 at 11:51
1
$\begingroup$

This is ancient history but I thought I'd post a quick alternative fix to the multiple-edge issue, in case this was useful to anyone (I taught this recently and came across this exact problem).

To begin with add vertices of degree $0$ so the graph has the same number of vertices on each side.

Now proceed as in the original proof; only if you were going to add an edge $xy$ there, instead add an entire new $K_{\Delta(G),\Delta(G)}$ with one of its edges $ab$ removed, and then also add edges $xb$ and $ya$.

$\endgroup$
  • $\begingroup$ Another similar approach is as follows. Take two disjoint copies of your bipartite graph. For every vertex with degree less than $\Delta(G)$, add an edge between the two copies of that vertex. This operation preserves the maximum degree and bipartiteness but increases the minimum degree. Repeat until regular. $\endgroup$ – Jon Noel Feb 12 at 0:19
0
$\begingroup$

I'm wondering if this is an appropriate solution, I'd love some feedback:

Let $G$ be a bipartite graph with $n>2$ vertices and assume that $X'(G) \lt \Delta(G)$. Recognize that the bipartite graph with $n$ vertices which contains the smallest possible $\Delta(G)$ is a simple path $P:=(v_1,e_1,v_2,e_2,..,e_{n-1},v_n)$ where each partition of the graph contains every other vertex. It is clear that in this case, $\Delta(G)=2$ which is a contradiction because a proper coloring which would correspond to $X'(G)=1$ is impossible in a connected graph with more than 2 vertices. Also, notice that a coloring of 2 is exactly $X'(G) =\Delta(G)=2$ and any coloring which uses more than 2 colors is not minimized.

On the other hand, the bipartite graph with $n$ vertices which contains a vertex which has the highest possible $\Delta(G)$ is the complete bipartite graph $K_{1,n-1}$. Here, the lone vertex in a partition of its own has $\Delta(G)=n-1$. Here we can see that a coloring $X'(G) \lt n-1$ is impossible because there are exactly $n-1$ incident edge. Notice that a coloring of exactly $X'(G) = \Delta(G)=n-1$ is the only proper coloring of $G$ and any color set which has more than $n-1$ elements is nonsensical (more colors than edges).

Therefore any bipartite graph with $n$>2 vertices has a chromatic edge coloring of $X'(G) = \Delta(G)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.