华东师范大学学报（自然科学版） >

2015 , Vol. 2015 >Issue 1: 114 - 119

DOI: https://doi.org/10.3969/j.issn.1000-5641.2015.01.013

应用数学与基础数学

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

  • 齐林明 ,
  • 苗连英 ,
  • 李卫奇
展开
  • 中国矿业大学 理学院, 江苏 徐州 221116
第一作者: 齐林明, 男, 硕士生,研究方向为图论及其应用. E-mail: 674752215@qq.com

收稿日期: 2014-03-01

  网络出版日期: 2015-03-29

基金资助

国家自然科学基金(11271365)

收起

On the independence number of edge chromatic critical graphs

  • QI Lin-Ming ,
  • MIAO Lian-Ying ,
  • LI Wei-Qi
Expand
  • College of Sciences, China University of Mining and Technology, Xuzhou Jiangsu 221116, China

Received date: 2014-03-01

  Online published: 2015-03-29

Fold

摘要

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

关键词： 边染色; 临界图; 独立数

本文引用格式

齐林明 , 苗连英 , 李卫奇 . 关于边染色临界图的独立数[J]. 华东师范大学学报（自然科学版）, 2015 , 2015(1) : 114 -119 . DOI: 10.3969/j.issn.1000-5641.2015.01.013

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

参考文献

VIZING V G. Some unsolved problems in graph theory [J]. Uaspekhi Mat Nauk 1968, 23: 117-134; Russian Math Surveys, 1968, 23: 125-142.
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.
逄世友, 马国翼, 苗连英. 临界图独立数的上界 [J]. 徐州师范大学学报: 自然科学版, 2010, 28(1): 15-16.
MIAO L Y. On the indepence number of edge chromatic critical graphs [J]. Ars Combinatoria, 2011, 98: 471-481.
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.
ZHANG L. Every planar graph with maximum degree 7 is of class 1 [J]. Graphs and combinatorics, 2000, 16: 467-495.
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.
LI S C, LI X C. Edge coloring of graphs with small maximum degree [J]. Discrete Mathematics, 2009, 309: 4843-4852.
Options
文章导航

/

〈 〉