Monday, 28 August 2006

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

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.

No comments:

Post a Comment