Definitions and notation
Let the multiplicity of vertices (nodes) v and w be the number of parallel edges that link them, and here too let be the largest multiplicity in . A graph is a multigraph for which .
An edge coloring of a (multi)graph is a mapping from the set of its edges to a set of items called colors, in such a way that at any vertex v, the edges there all have a different color. An edge--coloring is an edge-coloring where .
Note that a loop (an edge joining v to itself) accounts for two of the edges at v and cannot have a color different from itself, so edge-colorings as defined here do not exist for pseudographs (structures that are allowed to have loops).
For any multigraph (this includes graphs), we have of course
immediately from the definition. Surprisingly though, we also have
Theorem (Vizing) For any graph ,
This celebrated theorem was proved by V. G. Vizing in 1964 while still a graduate student (at Novosibirsk). It is a special case of
Theorem (Vizing) For any multigraph ,
(edge-coloring of multigraphs is the subject of Vizing’s doctoral thesis, 1965). The theorem was proved independently by R. P. Gupta in 1966; nowadays various versions of the proofs exist. A key rôle is played by connected subgraphs of colors and that cannot be extended further. They are analogous to Kempe chains in face or vertex colorings, but have a simpler structure: they are either paths or closed paths (the latter of even length). http://planetmath.org/node/6932See here for a proof (in the case of graphs).
Ore [Ore67] gives a sharper bound for multigraphs. Let the enlarged valency be given by
where w can be taken over all vertices of the graph; it effectively only ranges over those adjacent to v (as is zero for the others). Again, let denote the maximum enlarged valency occurring in . Now
Theorem (Ore) For any multigraph ,
The following theorem was proven in 1949 by Claude E. Shannon. He also gives examples, for any value of , of multigraphs that actually attain the bound, the so-called Shannon graphs: they have three vertices, with and .
Theorem (Shannon) For any multigraph ,
While giving a much worse bound for graphs, it gives for some multigraphs a better bound than Vizing’s theorem. Nevertheless, it is also possible to prove it from the latter [FW77].
Here too Ore [Ore67] gives a sharper bound based on the maximum of a local expression. Let be 0 if v has fewer than two neighbours, and otherwise
where and range over all pairs of distinct neighbours of v. Again, let be its largest value in the graph.
Theorem (Ore) For any multigraph ,
Vizing’s theorem has the effect of placing each multigraph in one of the classes 0, 1, 2, … where the class number is .
For graphs it means they split into just two classes: those that can be edge-colored in colors and those that need colors. The logical name for them would be class 0 and class 1; unfortunately the standard terminology is class 1 and 2 (or I and II).
Class I (graphs that can be edge--colored) contains among others
single -cycles for even
complete graphs for even
bipartite graphs (this is König’s theorem, 1916)
planar graphs with (by another theorem of Vizing)
planar graphs with ?? (conjecture of Vizing)
Class II (graphs that need colors) contains among others
single -cycles for odd
complete graphs for odd
for odd with a few edges missing (by a couple of theorems)
trivalent graphs with a bridge
but the general classification problem has thus far eluded the best efforts of Vizing and many others. There are interesting links here with polyhedral decompositions (aka cyclic double covers) and embeddings in surfaces.
Almost all graphs are in class I
Let be the number of graphs with vertices, and the number of them in class I.
Theorem (P. Erdős and R. J. Wilson)
So graphs of class II get relatively rarer for larger graph sizes. The absolute numbers do still increase. For cubic graphs for instance, we saw every one with a bridge is in class II. Bridgeless cubic graphs of class II are a bit thinner on the ground. By the four-color theorem, via Tait coloring, we know all of them are non-planar. Rarer still are those of them with girth at least five (and some non-triviality conditions); they are so hard to find that Martin Gardner dubbed them snarks. The Petersen graph is one, and a few infinite families of snarks have been found.
, so an edge--coloring must use alternating colors. For odd that’s impossible.
, note it is also the valency of every vertex. Fix two colors and . A Kempe chain can only terminate at a vertex where one of those colors is missing but in we cannot afford to miss any color at any vertex, so every is a cycle of even length and together they visit all vertices. For odd that’s impossible. For even there are ways to construct the coloring (try it).
and again the valency of every vertex. For the same reason as in the previous note, every or or is a cycle. Every edge must be in two such, but a bridge cannot be part of a cycle.
Oystein Ore, The Four-Color Problem,
Acad. Pr. 1967, ISBN 0 12 528150 1
Long the standard work on its subject, but written before the theorem was proven. Has a wealth of other graph theory material, including proofs of (improvements of) Vizing’s and Shannon’s theorems.
S. Fiorini and R. J. Wilson,
Edge-colourings of graphs, Pitman 1977,
ISBN 0 273 01129 4
The first ever book devoted to edge-colorings, including material previously found only in Russian language journal articles. Has proofs of Vizing’s and Shannon’s theorems.
Thomas L. Saaty and Paul C. Kainen,
The Four-Color Problem: assaults and conquest,
McGraw-Hill 1977; repr. Dover 1986, ISBN 0 486 65092 8
Wonderfully broad, not only focussing on the usual route to the Appel-Haken proof but also giving lots of other material.
Robert A. Wilson,
Graphs, Colourings and the Four-colour Theorem,
Oxford Univ. Pr. 2002, ISBN 0 19 851062 4 (pbk),
http://www.maths.qmul.ac.uk/ raw/graph.htmlhttp://www.maths.qmul.ac.uk/ raw/graph.html
A good general course in graph theory, with special focus on the four-color theorem and details of the Appel-Haken proof. Has proof of Vizing’s theorem.
|Date of creation||2013-03-22 15:10:36|
|Last modified on||2013-03-22 15:10:36|
|Last modified by||marijke (8873)|