图论及其应用徐俊明课后习题提示(12)

HintstoExercisesinChapter6

Ex6.1.4Letχ(G)=k.ThenGhasak-coloringπ=(V1,V2,···,Vk),whereViisanindependentsetofGand,hence,vi=|Vi|≤αforeach v i=1,2,···,k.

.(a)Sincev=v1+v2+···+vk≤kα,χ(G)=k≥αChooseanindependentsetIsuchthat|I|=α.ThenG Iis(v α)-colorable

clearly.Thus,χ(G)=k≤v+1 α.

1(b)Notethat(Vi,Vj)= sinceχ(G)=k.Thus,ε≥k(k 1),whichimplies 1k≤2+2ε+1.4

UsingExample1.2.2andLangrange’smethodofminimummultipliers,wehavethat

2ε≤ε(Tk,v)=k

i=1vi(v vi)=v 2k i=12vi≤v k2 v 2kv2=v .k2

v2

Thisimpliesk≥2.v 2ε

Ex6.1.5IfGcontainsnooddcycle,thenGisbipartiteand,hence,χ(G)≤2.AssumenowGcontainsanoddcycleC.ThenG Ccontainsnooddcycle.Thus,χ(G)≤χ(C)+χ(G C)≤3+2=5.

Ex6.1.6( )SinceGisk-critical,Gisnotanoddcycle.AlsosinceGisnotcomplete,k≤ byBrooks’theorem.Choosex∈V(G)suchthatdG(x)= .ByCorollary6.1.1,δ≥k 1,andsowehave

2ε=dG(x)= +dG(y)≥ +(v 1)δ

x∈Vy∈V\{x}

≥ +(v 1)(k 1)=( k)+v(k 1)+1

≥v(k 1)+1.

( )LetGbeaconnectedsimplegraphneitheranoddcyclenoracompletegraph,Hbeaχ(G)-criticalsubgraphofG.

AssumeHisanoddcycle.SinceGisnotanoddcycle,χ(G)=χ(H)=3≤ (G).AssumeHisacompletegraph.SinceGisnotacompletegraph,χ(G)<χ(G)+1≤ (G).

AssumeHisneitheranoddcyclenoracompletegraph.Sincek≥4,wehave

1,whichv (G)≥v (H)≥2ε(H)≥v(χ(G) 1)+1,thatis, (G)≥χ(G) 1+impliesχ(G)≤ (G).

Ex6.2.2Bycontradiction.Supposethatχ(G)= ,andletπ =(E1,E2,···,E )bea -edge-coloringofG.Since|Ei|≤α (G)foreachi=1,2,···, ,bythecondition(a),wehavecandeduceacontradictionasfollows.

α (G)<ε=

i=1|Ei|≤ α (G).

12

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库图论及其应用徐俊明课后习题提示(12)在线全文阅读。