21
$\begingroup$

I was wondering why there is (apparently) much more research directed towards vertex-coloring than edge-coloring? Prima facie, it seems that edge-coloring is just as "natural" a thing to investigate.

I can think of a few reasons:

  1. Vertex coloring is well behaved under deletion and contraction of edges.
  2. Vertex colorability is closely linked to the cycle matroid.
  3. Edge-coloring can be regarded as vertex-coloring restricted to line graphs.
  4. Since Vizing's theorem (that the chromatic index of $G$ is either $\Delta(G)$ or $\Delta(G)+1$) edge-coloring has been solved (asymptotically).

But is it really true that edge-coloring is less interesting than vertex-coloring?

$\endgroup$
8
  • 14
    $\begingroup$ Isn't reason 3 already pretty strong? One can't regard vertex coloring as a special case of edge coloring, so it seems to make sense to emphasize vertex colorings instead. $\endgroup$
    – Steven Sam
    Jan 7, 2010 at 1:49
  • 14
    $\begingroup$ Yes, but why study fields when we can study rings? Or why study groups when we could study monoids? $\endgroup$
    – Emil
    Jan 7, 2010 at 1:56
  • 4
    $\begingroup$ reason 4 is the best one for me ;) $\endgroup$ Jan 7, 2010 at 2:20
  • 1
    $\begingroup$ There are many applications of edge-coloring. $\endgroup$
    – Emil
    Jan 7, 2010 at 11:12
  • 4
    $\begingroup$ Most colouring problems arise from other mathematical structure (hypergraphs, posets, geometrical configurations, you name it), and it is rare that they correspond to edge colouring. It is basically reason #3. PS. I think this question should be community wiki. $\endgroup$
    – Boris Bukh
    Jan 7, 2010 at 15:26

8 Answers 8

19
$\begingroup$

There is a theorem involving edge colorings that is equivalent to the four color theorem. The assertion that every planar cubic bridgless graph has a three coloring of its edges is equivalent to the four color theorem. A bridge is an edge that when deleted increases the number of connected components. Finding a simple proof of this result would be an important result because the proof of the four color theorem is a complicated proof. There is an article available here on equivalents of the four color theorem

$\endgroup$
1
  • $\begingroup$ Yes but generally we can't transition between vertex- and edge- coloring - Tait's theorem is quite unusual in this regard. Are there other examples of where we can do this? $\endgroup$
    – Emil
    Jan 7, 2010 at 11:08
16
$\begingroup$

I don't think edge-coloring is considered less interesting. (Of course I don't think so, as it's one of my areas of research...) But I do think many people consider edge-coloring problems to be somewhat harder than vertex-coloring problems. The late Mike Albertson once told me that he thought of studying vertex coloring as wandering around in a dark forest, then looking up and discovering a small clearing---progress! He thought of studying edge coloring as wandering around in a dark forest, then looking up and discovering he was in the same place he started.

As for Vizing's Theorem... yes, any graph's edges can be colored using $\Delta$ or $\Delta+1$ colors; graphs in the former category are Class 1 and in the latter category are Class 2. Given a generic graph, it's not easy to tell into which Class the graph falls...even with plenty of information about the graph (example: graph is cubic and genus 1).

So my answer to your question is that there's less research done on edge-coloring because it's slightly harder than vertex-coloring is.

$\endgroup$
5
$\begingroup$

I do not know whether edge coloring is more or less interesting than vertex coloring, this is probably someting that could only be settled by a poll. The chief reasons why edge coloring receives less attention than vertex coloriong would, if I had to guess, be the third and fourth you offer.

Note though that if $X$ is $k$-regular graph, then Vizing's theorm tells us that its edge-chromatic number is $k$ or $k+1$. If it is $k$, then $X$ has a 1-factorization -- we can partition its edges into $k$ pairwise edge-disjoint perfect matchings. There is a very large literature on problems related to 1-factorizations.

Vertex coloring is also arguably more important in practice, since it arises in connection with important scheduling and register allocation problems. Although many of us are pure mathematicians and may feel no need to consider practical problems, the influence of the ``real world'' on pure mathematics is nonetheless very strong.

$\endgroup$
4
$\begingroup$

I actually do think that vertex-colouring is more interesting than edge-colouring, although I fully admit that this is my own personal bias. Instead of focusing on why edge-colouring is uninteresting, let me highlight why I think vertex-colouring is interesting.

Connections to topology. Along these lines there is of course the 4-colour theorem, Heawood's map conjecture, and Grötzsch's theorem. For planar graphs there is also a suitable notion of duality of colourings via flow-colouring duality. Kristal's answer is an instance of flow-colouring duality in action. That is, it suffices to prove the 4-colour theorem for planar triangulations. The dual of a planar triangulation is a cubic planar graph. So, it suffices to show that cubic planar graphs have 4-flows, and it's sort of an accident that 4-flows for cubic graphs actually correspond to 3-edge colourings.

Structural graph theory. Perhaps the most famous open problem in graph theory is Hadwiger's Conjecture, which connects vertex colouring to clique-minors. So, high chromatic number can actually force some structure, while high edge-chromatic number just forces high maximum degree.

$\endgroup$
1
  • $\begingroup$ What about if edge colorings are defined as a function of vertex coloring? Or if vertex colorings are defined as a function of edge colorings? Either of these situations would reduce the number of possible edge and vertex conjoint labelings. @tonyhuynh, is there a name for this kind of coloring where there are both edge and vertex labels simultaneously? $\endgroup$
    – ABh
    Aug 28, 2010 at 21:11
3
$\begingroup$

Historical accident? If I'm not mistaken one of the first graph coloring problems was the four-color theorem. By the time people started thinking about edge colorings the vertex-colorers might have just been far ahead.

(I suspect, though, that I may be committing the usual sin of repeating history as reported in mathematics textbooks. As we all know, this often bears only a tenuous relationship to real history.)

$\endgroup$
3
$\begingroup$

If you're going to be completely honest about the question, you need to consider edge colourings of multigraphs. Even in this case there are not a lot of open problems. Vizing's theorem already tells us that the chromatic index differs from the maximum degree by at most the maximum multiplicity. However, more is known:

  • We can compute the fractional chromatic index in polynomial time; even approximating the fractional chromatic number of a graph is hard.

  • The fractional chromatic index and the chromatic index agree asymptotically, as first proven by Kahn. However, the chromatic number is not even bounded by any function of the fractional chromatic number.

  • The Goldberg-Seymour conjecture implies that $\chi'_f$ and $\chi'$ differ by at most one. This is a long-standing open problem on the chromatic index. So what does that leave? Well, proving that the difference is bounded by some universal constant, but not too much else.

$\endgroup$
2
$\begingroup$

It is not an answer, but an other question.

When I was in school I proved that 4-color problem is equivalent to 3-color-edge coloring of planar graph with deg of each vertex =3.

Is this a known theorem? Does it have a name?

$\endgroup$
2
  • 1
    $\begingroup$ Yes it is knownI posted about it including a reference to an article containing that result. $\endgroup$ Jan 7, 2010 at 4:17
  • 4
    $\begingroup$ The edge coloring of 3-valent planar graphs with 3 colors is sometimes referred to as a Tait Coloring. In the dual, since planar graphs have duals, this means coloring the edges of triangles so that each triangle's edges get three different colors. $\endgroup$ Jan 7, 2010 at 4:29
1
$\begingroup$

I do not think that edge-coloring is necessarily less interesting than vertex-coloring. I work in neither but have used both in my research. I have a feeling that vertex-coloring may be perceived as more important in general graph theory, where the object of the study are graphs not necessarily with some particular structure and colorings are closely related to graph morphisms. Vertex color classes are independent sets, while edge-color classes are matchings. I found both concepts very useful.

However if the coloring is considered as part of the structure, it is hard to tell which concept is more popular. For instance, incidence geometries may be viewed as graphs with a given vertex-coloring. On the other hand, say, a Cayley graph is a graph that carries a natural edge-coloring structure.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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