亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        關(guān)于平面圖的7-全可染性的一個注記*

        2011-12-17 09:41:52王應(yīng)前
        關(guān)鍵詞:斷言平面圖頂點

        陶 鑫, 王應(yīng)前

        (浙江師范大學(xué)數(shù)理與信息工程學(xué)院,浙江金華 321004)

        本文的圖指的是有限簡單無向圖,文中未加定義的術(shù)語和記號參閱文獻[1].

        設(shè)G=(V,E)表示頂點集為V、邊集為 E的圖.若能用k種顏色對G進行染色,使得任意2個相鄰或相關(guān)聯(lián)的元素染有不同的色,則稱G是k-全可染的.設(shè)F,Δ和δ分別表示平面圖G的面集、最大度和最小度.顯然,給每一個圖進行全染色至少要用Δ+1個色.

        猜想1[1]任何簡單圖G都是(Δ+2)-全可染的.

        這一猜想被稱為全染色猜想,簡記為TCC.即使對于平面圖,TCC在目前還沒有得到完整證明.剩下未解決的情形是Δ=6[2-8].有趣的是,對于簡單平面圖,大多數(shù)情況是(Δ+1)-全可染的[9-10].

        猜想2[11]若G是4≤Δ≤8的簡單平面圖,則G是(Δ+1)-全可染的.

        對此,文獻[12]證明了Δ≥7且不含有4-圈的平面圖是(Δ+1)-全可染的;文獻[11]證明了Δ=7且不含相鄰三角形的平面圖是8-全可染的.筆者則研究了Δ=6且不含5-圈和6-圈的平面圖的全染色問題.

        定理1 若G是Δ=6且不含5-圈和6-圈的平面圖,則G是7-全可染的.

        證明 假設(shè)定理1不成立,并設(shè)G是定理1的一個使σ(G)=|V|+|E|最小的反例,即G本身不是7-全可染的,但它的每一個真子圖都是7-全可染的,則可得斷言1.

        斷言1[9]G是2-連通的,從而δ≥2且G的每個面的邊界都是圈.

        把度為k的點叫做k-點.類似地,度不小于k的點叫做k+-點,度不大于k的點叫做k--點.

        斷言2[12]設(shè) xy∈E.若 d(x)≤3,則 d(x)+d(y)≥Δ +2=8.特別地,G 中2-點只與6-點相鄰,3-點只與5+-點相鄰.

        斷言3 G不含圖1所示的結(jié)構(gòu).其中標(biāo)記為·的點在G中沒有其他鄰點.

        圖1 G不含有的構(gòu)形

        只證第5種情形(如圖1(e)所示),其他情形的證明可參閱文獻[10-11,13].假設(shè)G含有如圖1(e)所示的構(gòu)形.根據(jù) σ(G)的極小性知,G'=G -uv是7-全可染的.令 φ:V(G')∪E(G')→{1,2,…,7}是G'的一個7-全染色.設(shè)對于x∈V,S(x)是與頂點x以及與x相關(guān)聯(lián)的邊染得的顏色集.如圖1(e)所示,設(shè) S(u)={1,2,…,6},其中 φ(uq)=3,φ(uw)=4,φ(vm)=7,因此 φ(pq)=7.否則將 3 染給 uv,7 染給uq,這樣得到G的一個7-全染色,矛盾.此時交換pq與pw的顏色,將3染給uv,7染給uq,這樣得到了G的一個7-全染色,矛盾.因此,斷言3成立.

        以下將運用Discharging方法導(dǎo)出完成定理1證明所需要的矛盾.

        首先,給G的頂點v分配初始權(quán)ch(v)=2d(v)-6,給G的面f分配初始權(quán)ch(f)=d(f)-6.由握

        下面將定義一個權(quán)轉(zhuǎn)移規(guī)則,重新分配點和面的權(quán),并設(shè)ch'(x)是重新分配點和面的權(quán)后元素x∈于只是在同一個圖的點和面之間進行權(quán)轉(zhuǎn)移,權(quán)的總和應(yīng)該保持不變,因此得到 -12≥0,即得到了證明定理1所需要的矛盾.

        權(quán)轉(zhuǎn)移規(guī)則如下(如圖2所示):

        R1:轉(zhuǎn)向2-點的權(quán)

        與2-點相鄰的2個6-點都向此2-點轉(zhuǎn)移權(quán)1.

        R2:轉(zhuǎn)向3-面的權(quán)

        由斷言2知,3-面上只有1個3--點,因此

        R2.1:若3-面含有3--點,則此3-面上的2 個5+-點都向此

        R2.2:若3-面不含3--點,則此3-面上的3 個4+-點都向此3-面轉(zhuǎn)移權(quán) 1.

        R3:轉(zhuǎn)向4-面的權(quán)

        R3.1:若4-面含有2個3--點,則此4-面上的2個5+-點都向此4-面轉(zhuǎn)移權(quán)1;

        R3.2:若4-面含有1個3--點,則此4-面上與此3--點相對的那個4+-點向此

        R3.3:若4-面不含3--點,則此4-面上的4 個4+-點都向此4-面

        圖2 權(quán)轉(zhuǎn)移規(guī)則

        首先考察面的新權(quán).

        設(shè) f為3-面.若 f有1 個3--點,則根據(jù)R2.2,ch'(f)=ch(f)+1 ×3=0.

        設(shè) f為4-面.若 f含有2 個3--點,則根據(jù) R3.1,ch'(f)=ch(f)+1 ×2=0;若f含1 個3--點,則根據(jù)

        由G不含5-圈和6-圈知G不含5-面和6-面,故無需驗證5-面和6-面的新權(quán).

        設(shè)f為7+-面.由權(quán)轉(zhuǎn)移規(guī)則知f既不轉(zhuǎn)出權(quán)也不接受權(quán),因此ch'(f)=ch(f)=d(f)-6>0.

        綜上所述,對任意的面f∈F,ch'(f)≥0.

        其次考察頂點的新權(quán).

        設(shè)v為2-點.由斷言2和R1知,ch'(v)=ch(v)+1×2= -2+2=0.

        設(shè)v為3-點.由權(quán)轉(zhuǎn)移規(guī)則知v既不轉(zhuǎn)出權(quán)也不接受權(quán),故ch'(v)=ch(v)=0.

        下面用t表示與v關(guān)聯(lián)的3-面?zhèn)€數(shù).

        設(shè) v為4-點.由 G 不含5-圈和6-圈知 t≤2,且 v至少與2 個7+-面關(guān)聯(lián).根據(jù) R2.2 和 R2.3,v至多轉(zhuǎn)移權(quán)1給每個相關(guān)聯(lián)的3-面,至多轉(zhuǎn)移

        設(shè)v為5-點.由G不含5-圈和6-圈知t≤3,且v至少與2個7+-面關(guān)聯(lián).又由斷言3(如圖1(a)所示)知v至多與2個含有3--點的3-面關(guān)聯(lián),根據(jù)R2和R3

        設(shè)v為6-點.用n表示與v相鄰的2-點個數(shù),顯然,n≤6.與6-點相鄰的2-點分布情況如圖3所示.下面根據(jù)n的大小來討論v的新權(quán):

        圖3 與6-點相鄰的2-點分布情況(2≤n≤4)

        n=6.由斷言3(如圖1(d)所示)知,v不與3-面關(guān)聯(lián).由G不含5-圈和6-圈以及斷言3(如圖1(e)所示)知,與v關(guān)聯(lián)且關(guān)聯(lián)2個與v相鄰的2-點的面是7+-面.因此,v關(guān)聯(lián)6個7+-面,根據(jù)R1,

        n=5.由斷言3(如圖1(d)所示)知t=0.由G不含5-圈和6-圈知,v至少關(guān)聯(lián)5個7+-面,根據(jù)R1和R3,

        n=4.如圖3(a1)、圖 3(a2)、圖 3(a3)所示,由斷言3(如圖1(d)所示)知 t≤1.若 t=1,則由 G 不則v至少關(guān)聯(lián) 4個7+-面,根據(jù)R1和R3,ch'(v)≥ch(v)-1×4-1×2-0×4=0.

        n=3.如圖3(b1)、圖3(b2)、圖3(b3)所示,由斷言3(如圖1(d)所示)知 t≤2.若1≤t≤2,則由 G不含5-圈和6-圈知v至少關(guān)聯(lián)4個7+-面,根據(jù)R1,R2和R3,

        若 t=0,則 v至少關(guān)聯(lián)3個7+-面,根據(jù) R1和 R3,ch'(v)≥ch(v)-1×3-0×3-1×3=0.

        n=2.如圖3(c1)、圖3(c2)、圖3(c3)所示,由斷言 3(如圖1(d)所示)知 t≤2.若1≤t≤2,則由 G不含5-圈和6-圈知v至少關(guān)聯(lián)3個7+-面,根據(jù)R1,R2.1和R3,

        若t=0,則v至少關(guān)聯(lián)2個7+-面,根據(jù)R1和R3,ch'(v)≥ch(v)-1×2-0×2-1×4=0.

        設(shè)含有2-點的3-面是特殊3-面,記作s-面.由斷言3(如圖1(b)和圖1(c)所示)知,若6-點與一個s-面關(guān)聯(lián),則6-點不與其他含有3--點的3-面關(guān)聯(lián).

        n=1.若v與s-面關(guān)聯(lián),則由 G不含5-圈和6-圈知 t≤4,且 v至少關(guān)聯(lián)2個7+-面,根據(jù) R1,R2和

        若v不與s-面關(guān)聯(lián),則 t≤3.若t=3,則根據(jù)G不含5-圈和6-圈,v要關(guān)聯(lián)3個7+-面,從而

        若0≤t≤2,則v至少關(guān)聯(lián)2個7+-面,從而

        n=0.由G不含5-圈和6-圈知t≤4,且v至少關(guān)聯(lián)2個7+-面,根據(jù)R1,R2和R3,

        至此,對任意的x∈V∪F,ch'(x)≥0已得到驗證.定理1得證.

        [1]Bondy J A,Murty U S R.Graph theory[M].Berlin:Springer,2008.

        [2]Rosenfeld M.On the total coloring of certain graphs[J].Israel J Math,1971,9(3):396-402.

        [3]Kostochka A V.The total coloring of a multigraph with maximal degree 4[J].Discrete Math,1977,17(2):161-163.

        [4]Kostochka A V.The total chromatic number of any multigraph with maximal degree five is at most seven[J].Discrete Math,1996,162(2):199-214.

        [5]Borodin O V.On the total coloring of planar graphs[J].J Reine Angew Math,1989,394(2):180-185.

        [6]陳明,王應(yīng)前.關(guān)于平面圖全染色的一個注記[J].浙江師范大學(xué)學(xué)報:自然科學(xué)版,2007,30(4):421-423.

        [7]Sanders D P,Zhao Yue.On total 9-coloring planar graphs of maximum degree seven[J].J Graph Theory,1999,319(1):67-73.

        [8]Wang Yingqian,Shangguan Minle,Li Qiao.On total chromatic number of planar graphs without 4-cycles[J].Sci China Ser A,2007,50(1):81-86.

        [9]Borodin O V,Kostochka A V,Woodall D R.Total coloring of planar graphs with large maximum degree[J].J Graph Theory,1997,26(1):53-59.

        [10]Wang Weifan.Total chromatic number of planar graphs with maximum degree ten[J].J Graph Theory,2007,54(1):91-102.

        [11]Du Dingzhu,Shen Lan,Wang Yingqian.Planar graphs with maximum degree 8 and without adjacent triangles are 9-totally-colorable[J].Discrete Appl Math,2009,157(1):2778-2784.

        [12]Hou Jianfeng,Liu Guizhen,Cai Jiansheng.List edge and list total coloring of planar graphs without 4-cycles[J].Theoret Comput Sci,2006,369(4):250-255.

        [13]Kowalik L,Sereni J S,Skrekovski R.Total coloring of plane graphs with maximum degree nine[J].SIAM J Discrete Math,2008,22(4):1462-1479.

        猜你喜歡
        斷言平面圖頂點
        von Neumann 代數(shù)上保持混合三重η-*-積的非線性映射
        C3-和C4-臨界連通圖的結(jié)構(gòu)
        過非等腰銳角三角形頂點和垂心的圓的性質(zhì)及應(yīng)用(下)
        特征為2的素*-代數(shù)上強保持2-新積
        《別墅平面圖》
        《別墅平面圖》
        《景觀平面圖》
        Top Republic of Korea's animal rights group slammed for destroying dogs
        關(guān)于頂點染色的一個猜想
        平面圖的3-hued 染色
        精品无码国产自产在线观看水浒传 | 亚洲精品永久在线观看| 波多野结衣一区二区三区免费视频| 东京热日本道免费高清| 精品欧美一区二区三区久久久| 天天天天躁天天爱天天碰| 精品国产91天堂嫩模在线观看| 国产精品一区二区三区黄片视频| 东北女人一级内射黄片| 男女上下猛烈啪啪免费看| 亚洲区在线播放| 国产精品一区二区黄色片| 亚洲av中文无码乱人伦在线观看| 一性一交一口添一摸视频| 亚洲色欲久久久综合网 | 亚洲电影一区二区三区 | 麻豆国产在线精品国偷产拍| 亚洲成a人片在线看| 东京道一本热码加勒比小泽| 水蜜桃在线观看一区二区| 中文字幕精品久久久久人妻红杏ⅰ| 亚洲A∨无码国产精品久久网| 亚洲无人区乱码中文字幕| 尹人香蕉久久99天天拍| 日本阿v网站在线观看中文 | 职场出轨的人妻中文字幕| 中文字字幕在线精品乱码 | 少妇被日到高潮的视频| 日本在线一区二区三区不卡| 国产卡一卡二卡三| 亚洲中文欧美日韩在线| 日本岛国一区二区三区四区| 国产成人av综合色| 亚洲一区日韩无码| 日本一级二级三级在线| 精品久久久久久亚洲综合网| 亚洲av伊人久久综合密臀性色| 97无码人妻一区二区三区蜜臀 | 亚洲国产人在线播放首页| 久久久精品国产视频在线| 色婷婷精品久久二区二区蜜臀av|