Why is edge-coloring less interesting than vertex-coloring?

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.)

Answer 6

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.

Answer 7

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?

Answer 8

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.