齊林明，苗連英，李衛(wèi)奇

（中國礦業(yè)大學理學院，江蘇徐州221116）

關于邊柒色臨界圖的獨立數(shù)

齊林明，苗連英，李衛(wèi)奇

（中國礦業(yè)大學理學院，江蘇徐州221116）

1968年，Vizing提出猜想：邊染色臨界圖的獨立數(shù)不大于其階數(shù)的一半.針對不含2度點的邊染色臨界圖，本文證明當最大度為9，10時，獨立數(shù)α（G）≤|V|和當Δ∈｛11，···，46｝時，獨立數(shù)α（G）≤

邊染色；臨界圖；獨立數(shù)

0引言

本文中G是有n個頂點、m條邊、最大度為Δ的簡單圖.k點是指度數(shù)為k的點，G的Δ點被稱為G的主頂點.用d（x）來表示x點的度數(shù)，α（G）表示獨立數(shù)，Δ（G）表示最大度點，δ（G）表示最小度點，N（x）表示與x相鄰接的鄰點.

1965年，Vizing證明了：最大度為Δ的圖G，其邊色數(shù)χ′（G）要么是Δ，要么是Δ+1.如果χ′（G）=Δ，則稱圖G是第一類的；如果χ′（G）=Δ+1.則稱圖G是第二類的.如果圖G是連通的和第二類的，且對每條邊χ′（G-e）＜χ′（G），則稱G是臨界圖.1968年，Vizing提出了如下臨界圖獨立數(shù)的猜想［1］：若G是n階Δ臨界圖，則有α（G）≤.

2000年，Birnkmann證明了：

（2）如果G是一個n階臨界圖，則對較小的最大度，有

2004年，Geunewald和Steffen證明了此猜想在邊數(shù)很多的時候成立.2009年，Luo等證明了［2］：對于Δ∈｛11,12···,29｝，有

2010年，逄世友等證明了［3］：若臨界圖的某一最大獨立集至多包含一個主頂點，則獨立數(shù)猜想成立.2011年，苗連英證明了［4］：對于Δ∈｛11,12···,29｝有

本文則得到了如下結果.

定理1對于不含2度點的邊染色臨界圖，當最大度為9,10時，獨立數(shù)α（G）≤|V|；當Δ∈｛11,···,46｝，獨立數(shù)α（G）≤|V|.

1引理

引理2.1（V AL）［1］設G是Δ臨界圖，xy∈E（G），則：

（1）x至少與Δ-d（y）+1個Δ點相鄰.

（2）至少兩個Δ點與x相鄰.

引理2.2［5,6］G是Δ臨界圖，xy∈E（G），且d（x）+d（y）=Δ+2，則

（1）每個N（x,y）｛x,y｝的點的度數(shù)為Δ；

（2）每個N（N（x,y））｛x,y｝的點的度數(shù)至少為Δ-1；

（3）如果d（x）,d（y）＜Δ，每個N（N（x,y））｛x,y｝點都為Δ點.

引理2.3［7］G是Δ臨界圖，Δ≥5，x是一個3點，那么N（x）中至少有兩個主頂點，它們不相鄰于任何除x之外的（≤Δ-2）點.

引理2.4［7］G是Δ臨界圖，Δ≥6，x是一個4點.

（1）若x相鄰于一個（Δ-2），記為y，那么N（N（x））｛x,y｝?VΔ；

（2）若x不與任何（Δ-2）點相鄰且x的某一鄰點y相鄰于d（y）-（Δ-3）個（≤Δ-2）點，那么x的另外三個鄰點不與任何除x之外的（≤Δ-2）點相鄰.

（3）若x與一個（Δ-1）點相鄰，那么N（x）中至少有兩個主頂點至多與兩個（≤Δ-2）點相鄰.進一步，若x與兩個（Δ-1）點相鄰，那么與x相鄰的另兩個主頂點不與任何除x之外的（≤Δ-2）點相鄰.

引理2.5［8］G是Δ臨界圖，x是一個5點，假設x有一個（Δ-2）鄰點ω

（1）若ω與一個除x外的（≤Δ-2）點鄰接，則x的其余四個鄰點全部為Δ點且它們的鄰點除x外全部為（≥Δ-1）.

（2）若ω只鄰接一個（≤Δ-2）點x，則x的其余三個（≥Δ-1）的鄰點包括至少兩個Δ點y滿足以下情況：若是一個Δ點，則至多鄰接兩個（≤Δ-2）點；若為（Δ-1）度點，則只鄰接一個（≤Δ-2）的點x.

引理2.6［4］G是Δ臨界圖，Δ≥9，x是一個5點，若x不鄰接任何（≤Δ-2）點且若x的一個鄰點鄰接四個（≤Δ-3）點，則x的其余四個鄰點只鄰接一個（≤Δ-3）的點x.

2定理1的證明

設G=（V,E）是Δ臨界圖，S?V是一個獨立集，令T=V-S.令Si表示S中i點的個數(shù)，i∈｛3,4···,Δ｝.令A=｛vtvs∈E|vt∈T,vs∈S，且d（vs）＜Δ｝，Ai=｛vtvs∈E|vt∈T,vs∈S,d（vs）=i｝.顯然，|Ai|=isi.按下面的方式定式函數(shù)f（vtvs）：A→R，vt∈T,vs∈S.

（1）d（vs）/=3,4,5時，那么

（2）d（vs）=3.當vt和S中除vs之外的一個（≤Δ-2）點相鄰時，其他情況，

（3）d（vs）=4.如果vt和S中除vs之外的兩個（≤Δ-2）點相鄰，那么；如果vt和S中除vs之外的一個（≤Δ-2）點相鄰，那么；如果vt不與S中除vs之外的一個（≤Δ-2）點相鄰，那么

（4）d（vs）=5.如果vt和S中除vs之外的三個（≤Δ-3）點相鄰，那么f（vtvs）==；如果vt和S中除vs之外的三個（≤Δ-2）點相鄰（至少有一個點為（Δ-2）），）表示在S中vt的5點鄰點和N-（vt,vs）在N（vt）∩Svs中（≤Δ-2）點的集合，并且在這種情況下如果vt和S中除vs之外的兩個（≤Δ-2）點相鄰且這兩個（≤Δ-2）全部為（Δ-3）點，那么f（vtvs）=；如果vt和S中除vs之外的一個（≤Δ-2）點相鄰，f（vtvs）=；如果vt不與S中除vs之外的（≤Δ-2）相鄰，那么f（vtvs）=

取T中的一點v.若v不與S中的3,4,5點相鄰，令d表示v在S中的鄰點最小的度數(shù).由引理2.1得，v至多與A中的d-1條邊關聯(lián).因此得到

若v與S中的一個3點u相鄰，由引理2.1得，v至多與S中一個異于u的（≤Δ-1）點相鄰.如果v不與S中異于u的（≤Δ-1）點相鄰，那么；如果V與任何S中異于u的一個（≤Δ-1）點相鄰，記為w：如果d（w）/=｛3,4,5｝由d（w）/=2，f（vu）+f（vw）=+=1；如果d（w）=4，由（3）可知，如果d（w）=5，由（4）可知

若v與S中的一個4點u相鄰，由引理2.1得，v至多與S中兩個異于u的（≤Δ-1）的點相鄰.如果v不與任何S中異于u的（≤Δ-2）點相鄰，則由（3）可知，f（vu）=，則有如果v與S中異于u的一個（≤Δ-2）點相鄰，記為w，則由d（w）=4,5或≥6有，1或如果v和S中除vs之外的兩個（≤Δ-2）點相鄰，記為w,z，則根據(jù)（3）有，若｛d（w）,d（z）｝=｛4,4｝,｛4,5｝,｛5,5｝,｛5,i（6≤i≤Δ-3）｝,｛5,j（j≥Δ-2）｝或｛k（k≥6）,l（l≥6）｝，則有1或

若v與S中的一個5點u相鄰，由引理2.1得，v最多與S中三個異于u的（≤Δ-1）有的點相鄰.如果v不與s中異于u的（≤Δ-2）點相鄰，則通過（4）可知，f（vu）=如果v與S中異于u的一個（≤Δ-2）點相鄰，記為w，則由d（w）=5或d（w）≥6，有如果v與S中異于u的兩個（≤Δ-2）點相鄰，記為w,z，則通過（4）可知，根據(jù)｛d（w）,d（z）｝=｛5,5｝,｛5,i（6≤i≤Δ-3）｝,｛5,j（j≥Δ-2）｝或｛k（k≥6）,l（l≥6）｝，則有如果v與S中異于u的三個（≤Δ-3）點相鄰，記為w，y，z，則通過（4）知，；如果v與S中異于u三個的（≤Δ-2）點（至少一個點為Δ-2點）相鄰，則通過（4）可知：

首先考慮f（e），由引理2.3，對任意3點vs∈S，vs至少與T中兩個主頂點相鄰，且這兩個主頂點不與除vs之外的（≤Δ-2）點相鄰.由此據(jù)（2）可知，S中任一3點至少關聯(lián)A3中的兩條邊的大小.

綜上，我們有

因為G為臨界圖，所以上式不等號嚴格成立.將式（2）與（3）進行線性組合：（2）+（3），得到

經(jīng)驗證，對于i∈｛3,4,5···,Δ-1｝，且9≤Δ≤，si的系數(shù)非負，因此Δ∈｛9,10｝.所

對于Δ∈｛9,10｝，我們有將式（2）與式（3）進行線性組合：（2）+8Δ 7（Δ-6）（3）.得

經(jīng)驗證，當i∈｛3,4,5｝，Δ＞10,ai＞0且當.所以，當

3結論

綜上，對于n階Δ臨界圖G，若G不含2度點，則

［1］VIZING V G.Some unsolved problems in graph theory［J］.Uaspekhi Mat Nauk 1968，23：117-134；Russian Math Surveys，1968，23：125-142.

［2］LUO R，ZHAO Y.An application of Vizing and Vizing-like adjacency lemmes to Vizing's indenpence number conjecture of edge chromatic critical graphs［J］.Discrete Mathematics，2009，309：2925-2929.

［3］逄世友，馬國翼，苗連英.臨界圖獨立數(shù)的上界［J］.徐州師范大學學報：自然科學版，2010，28（1）：15-16.

［4］MIAO L Y.On the indepence number of edge chromatic critical graphs［J］.Ars Combinatoria，2011，98：471-481.

［5］SANDERS D，ZHAO Y.Planar graphs with maximum degree seven are Class 1［J］.Critical Graphs：J Combin Theory Ser B，2001，83：201-212.

［6］ZHANG L.Every planar graph with maximum degree 7 is of class 1［J］.Graphs and combinatorics，2000，16：467-495.

［7］LUO R，MIAO L Y，ZHAO Y.The size of edge chromatic critical graphs with maximum degree 6［J］.Graphs Theory，2009，60：149-171.

［8］LI S C，LI X C.Edge coloring of graphs with small maximum degree［J］.Discrete Mathematics，2009，309：4843-4852.

（責任編輯王善平）

On the independence number of edge chromatic critical graphs

QI Lin-ming，MIAO Lian-ying，LI Wei-qi
（College of Sciences，China University of Mining and Technology，Xuzhou Jiangsu221116，China）

In1968，Vizing conjectured for any edge chromatic critical graph G=（V，E）with maximum degree Δ and independence number α（G），α（G）≤. In this paper，we proved that α（G）≤|V|for Δ∈｛9，10｝and α（G）≤|V|for Δ∈｛11，···，46｝.

edge coloring；critical graphs；independence number

O157.5

A

10.3969/j.issn.1000-5641.2015.01.013

1000-5641（2015）01-0114-06

2014-03

國家自然科學基金（11271365）

齊林明，男，碩士生，研究方向為圖論及其應用.E-mail：674752215@qq.com.

苗連英，女，教授，研究方向為圖論及其應用.E-mail：miaolianying@cumt.edu.cn.