华东师范大学学报(自然科学版) ›› 2015, Vol. 2015 ›› Issue (1): 114-119.doi: 10.3969/j.issn.1000-5641.2015.01.013

• 应用数学与基础数学 • 上一篇    下一篇

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

齐林明,苗连英,李卫奇   

  1. 中国矿业大学 理学院, 江苏 徐州 221116
  • 收稿日期:2014-03-01 出版日期:2015-01-25 发布日期:2015-03-29
  • 通讯作者: 苗连英, 女, 教授,研究方向为图论及其应用. E-mail:miaolianying@cumt.edu.cn
  • 作者简介:第一作者: 齐林明, 男, 硕士生,研究方向为图论及其应用. E-mail: 674752215@qq.com
  • 基金资助:

    国家自然科学基金(11271365)

On the independence number of edge chromatic critical graphs

 QI  Lin-Ming, MIAO  Lian-Ying, LI  Wei-Qi   

  1. College of Sciences, China University of Mining and Technology, Xuzhou Jiangsu 221116, China
  • Received:2014-03-01 Online:2015-01-25 Published:2015-03-29

PDF

1540

摘要： 1968年, Vizing提出猜想:边染色临界图的独立数不大于其阶数的一半.针对不含2度点的边染色临界图, 本文证明当最大度为9,10时，独立数α(G) ≤(3Δ-3)/(5Δ-3)|V|和当Δ∈{11, · · · , 46}时, 独立数α(G) ≤(15Δ-42)/(23Δ-42)|V|

关键词: 边染色, 临界图, 独立数

Abstract: In 1968, Vizing conjectured for any edge chromatic critical graph G = (V,E) with maximum degree Δ and independence number α(G), α(G)≤|V|/2. In this paper, we proved that α(G) ≤(3Δ-3)/(5Δ-3)|V| for Δ∈{9,10} and α(G) ≤(15Δ-42)/(23Δ-42)|V| for Δ∈{11, · · · , 46}

Key words: edge coloring, critical graphs, independence number

中图分类号: