关于边柒色临界图的独立数

齐林明，苗连英，李卫奇

（中国矿业大学理学院，江苏徐州221116）

关于边柒色临界图的独立数

齐林明，苗连英，李卫奇

（中国矿业大学理学院，江苏徐州221116）

1968年，Vizing提出猜想：边染色临界图的独立数不大于其阶数的一半.针对不含2度点的边染色临界图，本文证明当最大度为9，10时，独立数α（G）≤|V|和当Δ∈｛11，···，46｝时，独立数α（G）≤

边染色；临界图；独立数

0引言

本文中G是有n个顶点、m条边、最大度为Δ的简单图.k点是指度数为k的点，G的Δ点被称为G的主顶点.用d（x）来表示x点的度数，α（G）表示独立数，Δ（G）表示最大度点，δ（G）表示最小度点，N（x）表示与x相邻接的邻点.

1965年，Vizing证明了：最大度为Δ的图G，其边色数χ′（G）要么是Δ，要么是Δ+1.如果χ′（G）=Δ，则称图G是第一类的；如果χ′（G）=Δ+1.则称图G是第二类的.如果图G是连通的和第二类的，且对每条边χ′（G-e）＜χ′（G），则称G是临界图.1968年，Vizing提出了如下临界图独立数的猜想［1］：若G是n阶Δ临界图，则有α（G）≤.

2000年，Birnkmann证明了：

（2）如果G是一个n阶临界图，则对较小的最大度，有

2004年，Geunewald和Steffen证明了此猜想在边数很多的时候成立.2009年，Luo等证明了［2］：对于Δ∈｛11,12···,29｝，有

2010年，逄世友等证明了［3］：若临界图的某一最大独立集至多包含一个主顶点，则独立数猜想成立.2011年，苗连英证明了［4］：对于Δ∈｛11,12···,29｝有

本文则得到了如下结果.

定理1对于不含2度点的边染色临界图，当最大度为9,10时，独立数α（G）≤|V|；当Δ∈｛11,···,46｝，独立数α（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｝的点的度数为Δ；

（2）每个N（N（x,y））｛x,y｝的点的度数至少为Δ-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点的个数，i∈｛3,4···,Δ｝.令A=｛vtvs∈E|vt∈T,vs∈S，且d（vs）＜Δ｝，Ai=｛vtvs∈E|vt∈T,vs∈S,d（vs）=i｝.显然，|Ai|=isi.按下面的方式定式函数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中的邻点最小的度数.由引理2.1得，v至多与A中的d-1条边关联.因此得到

若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，则根据（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）可知，根据｛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）点相邻.由此据（2）可知，S中任一3点至少关联A3中的两条边的大小.

综上，我们有

因为G为临界图，所以上式不等号严格成立.将式（2）与（3）进行线性组合：（2）+（3），得到

经验证，对于i∈｛3,4,5···,Δ-1｝，且9≤Δ≤，si的系数非负，因此Δ∈｛9,10｝.所

对于Δ∈｛9,10｝，我们有将式（2）与式（3）进行线性组合：（2）+8Δ 7（Δ-6）（3）.得

经验证，当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］逄世友，马国翼，苗连英.临界图独立数的上界［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.