请输入您要查询的字词:

 

单词 VizingsTheorem
释义

Vizing’s theorem


\\PMlinkescapephrase

class numberMathworldPlanetmathPlanetmath

Definitions and notation

In a graph or multigraphMathworldPlanetmath G, let ρ(v) denote the valencyPlanetmathPlanetmath of vertex(node) v, and let ρ(G) denote the largest valency in G (often writtenjust ρ on its own, Δ(G) is another common notation).

Let the multiplicityMathworldPlanetmath μ(v,w) of vertices (nodes) v and wbe the number of parallel edges that link them, and here too let μ(G) bethe largest multiplicity in G. A graph is a multigraph for which μ(G)=1.

An edge coloringMathworldPlanetmath of a (multi)graph G is a mapping from theset E of its edges to a set K of items called colors, in such a waythat at any vertex v, the ρ(v) edges there all have a differentcolor. An edge-k-coloringMathworldPlanetmath is an edge-coloring where |K|=k.

Note that a loop (an edge joining v to itself) accounts for two of theρ(v) edges at v and cannot have a color different from itself,so edge-colorings as defined here do not exist for pseudographsMathworldPlanetmath (structuresMathworldPlanetmaththat are allowed to have loops).

The chromatic index (aka edge-chromatic number) χ(G) isthe smallest number k for which an edge-k-coloring of G exists. This nowstandard notation is analogous to the chromatic numberMathworldPlanetmath χ(G) whichrefers to vertex coloring.

Vizing’s theorem

For any multigraph G (this includes graphs), we have of course

χ(G)ρ(G)

immediately from the definition. Surprisingly though, we also have

Theorem (Vizing)For any graph G,

χ(G)ρ(G)+1

This celebrated theorem was proved by V. G. Vizing in 1964 while still agraduate student (at Novosibirsk). It is a special case of

Theorem (Vizing)For any multigraph G,

χ(G)ρ(G)+μ(G)

(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 variousversions of the proofs exist. A key rôle is played by connected subgraphsMathworldPlanetmath H(a,b) of colors a and b that cannot be extended further. They are analogous to Kempe chainsMathworldPlanetmath 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 theenlarged valency ρ+(v) be given by

ρ+(v)=defρ(v)+maxwμ(v,w)

where w can be taken over all vertices of the graph; it effectively onlyranges over those adjacent to v (as μ(v,w) is zero for the others).Again, let ρ+(G) denote the maximum enlarged valency occurring inG. Now

Theorem (Ore) For any multigraph G,

χ(G)ρ+(G)

Shannon’s theorem

The following theorem was proven in 1949 byClaude E. Shannon. He also gives examples, for any value of ρ, ofmultigraphs that actually attain the bound,the so-called Shannon graphs: they have three vertices, withμ(a,b)=μ(a,c)=ρ/2 andμ(b,c)=ρ/2.

Theorem (Shannon) For any multigraph G,

χ(G)32ρ(G)

While giving a much worse bound for graphs, it gives for some multigraphs abetter bound than Vizing’s theorem. Nevertheless, it is also possible to proveit from the latter [FW77].

Only in the context of graph coloringsMathworldPlanetmath is Shannon’s theorem understoodto refer to the one here; in the wider world the term tends to refer to any ofhis fundamental theorems in information theory.

Here too Ore [Ore67] gives a sharper bound based on the maximum ofa local expression. Let σ(v) be 0 if v has fewer than twoneighbours, and otherwise

σ(v)=defmaxv,v′′(ρ(v)+ρ(v)+ρ(v′′))

where v and v′′ range over all pairs of distinct neighbours of v. Again, let σ(G) be itslargest value in the graph.

Theorem (Ore) For any multigraph G,

χ(G)max(ρ(G),12σ(G))

Chromatic class

Vizing’s theorem has the effect of placing each multigraph G in one of theclasses 0, 1, 2, … μ(G) where the class number isχ(G)-ρ(G).

For graphs it means they split into just two classes: those that can beedge-colored in ρ(G) colors and those that need ρ(G)+1colors. The logical name for them would be class 0 and class 1; unfortunatelythe standard terminology is class 1 and 2 (or I and II).

Class I (graphs that can be edge-ρ-colored) contains among others

  • single n-cycles for even n

  • complete graphsMathworldPlanetmath Kn for even n

  • bipartite graphsMathworldPlanetmath (this is König’s theorem, 1916)

  • bridgeless planar trivalent graphs (four-color theorem via Tait coloringMathworldPlanetmath)

  • planar graphsMathworldPlanetmath with ρ(G)8 (by another theorem of Vizing)

  • planar graphs with ρ(G)6?? (conjecture of Vizing)

Class II (graphs that need ρ+1 colors) contains among others

  • single n-cycles for odd n

  • complete graphs Kn for odd n

  • Kn for odd n 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 ofVizing and many others. There are interesting links here with polyhedraldecompositions (aka cyclic double covers) and embeddingsPlanetmathPlanetmathPlanetmath in surfaces.

A(n edge-)critical graph is a connected graph of class II but suchthat removing any of its edges makes it class I. As often in graph theoryMathworldPlanetmath,such a minimality condition imposes a certain amount of structure on the graph.There are conjectures…

Almost all graphs are in class I

Let #Gn be the number of graphs with n vertices,and #GnI the number of them in class I.

Theorem (P. Erdős and R. J. Wilson)

limn#GnI#Gn=1

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 graphMathworldPlanetmathPlanetmath is one, and a few infiniteMathworldPlanetmath families of snarks have been found.

ρ=2, so an edge-ρ-coloring must use alternating colors. For odd n that’s impossible.

ρ=n-1, note it is also the valency of every vertex.Fix two colors a and b. A Kempe chain H(a,b) can only terminate at a vertex where one of those colors is missing but in Kn we cannot afford to miss any color at any vertex, so every H(a,b) is a cycle of even length and together they visit all n vertices. For odd n that’s impossible.For even n there are ways to construct the coloring (try it).

ρ=3 and again the valency of every vertex. For the samereason as in the previous note, every H(a,b) or H(c,a) or H(b,c) is a cycle. Every edge must be in two such, but a bridge cannot be part of a cycle.

References

  • 1
  • Ore67 Oystein Ore, The Four-Color Problem,
    Acad. Pr. 1967, ISBN  0 12 528150 1
    Long the standard work on its subject, but written beforethe theorem was proven. Has a wealth of other graph theorymaterial, including proofs of (improvements of) Vizing’s andShannon’s theorems.
  • FW77 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 RussianlanguagePlanetmathPlanetmath journal articles. Has proofs of Vizing’s andShannon’s theorems.
  • SK77 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 usualroute to the Appel-Haken proof but also giving lots ofother material.
  • Wil02 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(errata &c.)
    A good general course in graph theory, with special focus onthe four-color theorem and details of the Appel-Haken proof.Has proof of Vizing’s theorem.
随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/5 2:47:00