请输入您要查询的字词:

 

单词 ProofOfVizingsTheoremforGraphs
释义

proof of Vizing’s theorem (for graphs)


Proof of Vizing’s theorem (for graphs)

We must prove, for any integer ρ, the following: if G is a graph all ofwhose vertices have valencyPlanetmathPlanetmath ρ, then its edges can be colored (withadjacent edges receiving different colors) in no more than ρ+1 colors.

This form of stating the theorem allows us to do inductionMathworldPlanetmath on thenumber of edges. A graph with zero edges, for instance, certainly doesn’tneed more than ρ+1 colors. Now assume (for any given ρ) thatall graphs with m edges can be thus colored. For any graph G with m+1edges we choose an edge to remove, color the remaining m edges, andtry putting the edge back.

Another way of looking at this: suppose there was (for a certain ρ) agraph G* with m* edges that could not be colored thus. There would thenbe a largest number m, boundedPlanetmathPlanetmathPlanetmathPlanetmath by 0m<m*, such that all graphs withm edges can still be colored thus. Then there would also be a G with m+1edges that cannot. Choose one of its edges and proceed as above. This time,succeeding in coloringMathworldPlanetmath it after all would prove by contradictionMathworldPlanetmathPlanetmath that therewas no such m and hence no such G*.

Either way we have our G where after picking an edge we can color everythingexcept that edge, and fitting it in too proves the theorem. Let the edge tofit run between v and w1. Some terms:

  • With a palette of ρ+1 edge colors, and no more than ρ edgesat any vertex, each vertex has at least one missing color.

  • Let a Kempe chainMathworldPlanetmath H(a,b) be any connected componentMathworldPlanetmathPlanetmathPlanetmathPlanetmath of thesubgraphMathworldPlanetmath formed by all edges colored a or b. This is either acycle of even length, or an open path terminating at two verticeswhere one of a or b is missing.

Step 1. If there is a color missing both at v and at w1, usethat color for the edge vw1 and we’re finished.

Else, let color a be missing at v (but present at w1), and colorb1 be missing at w1 (but present at v). If the Kempe chain ofcolors a and b1 that terminates at v is disjoint from the oneterminating at w1, swap the colors in the latter chain, then usea for edge vw1 and be done.

Else it’s the same H(a,b1) chain, in which case we proceed as follows.




vw1H(a,b1)

Find the b1-colored edge from v, call itvw2. Steal color b1 from it and give it to edge vw1, nowvw2 is the problem edge that needs a color.




vw1w2H(a,b1)

Go back to Step 1 calling it Step 2, replacing subscripts 1 by 2in all text. This involves a color b2 that was missing at w2 (aremains the missing color at v). If v and w2 are awkward too,being in the same H(a,b2) chain




vw1w2H(a,b1)H(a,b2)

find the b2-colored edge vw3, give its color to vw2making vw3 the problem:




vw1w2w3H(a,b1)H(a,b2)

Next time round (Step 3) increase the subscripts again.And if still necessary, transfer the color again.



.............
.............vw1w2w3w4H(a,b1)H(a,b2)H(a,b3)

Sooner or later (if we don’t get to bail out at one of the Steps) we will runout of colors, in the following sense: the color missing at some wj+1is not some new color bj+1 but a color bi we’ve seen before (it can’tbe a, that’s present at wj+1). And not only is i<j+1 but alsoi<j because bj is the color we just stole from wj+1.

A chain H(a,bi) runs from v to wi+1 and all its verticesexcept wi+1 have color bi. Now wj+1 isn’t wi+1(because i<j) nor one of the other vertices of the chain (becauseit doesn’t have color bi). So wj+1 isn’t on this H(a,bi).




vwiwi+1wj+1H(a,bi)

wk+1 does have color a so it’s on some other H(a,bi) disjointfrom H(a,bi). This could be as short as a single a-colored edge orlonger, it doesn’t matter.




vwiwi+1wj+1H(a,bi)H(a,bi)

Swap the colors in that H(a,bi). Now use a to finally colorvwj+1 (merging H(a,bi) and H(a,bi) in the process).




vwiwi+1wj+1H(a,bi)H(a,bi)

This is in essence the proof usually given, as taught to students and found for instance in references [FW77] and [Wil02] of thehttp://planetmath.org/node/6930parent entry.

随便看

 

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

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 15:01:23