| 边染色临界图主顶点数的一个结果 |
| |
| 引用本文： | 田大东,张埂,李梅. 边染色临界图主顶点数的一个结果[J]. 山东师范大学学报(自然科学版), 2013, 0(4): 7-9 |
| |
| 作者姓名： | 田大东 张埂 李梅 |
| |
| 作者单位： | [1]青岛理工大学临沂校区基础课教学部,山东费县273400 [2]四川文理学院,,四川达州635000 |
| |
| 摘 要： | 如果一个连通的第二类图G去掉任意一条边后其边色数都比图G小,则称它是一个临界图.最大顶点度为△的临界图称作△-临界图.1968年,Vizing猜想任意n阶△-临界图G边数m的下界为（nΔ-n＋3）/2.Fiorini不等式和差值转移法被广泛用于研究此猜想.笔者利用Vizing邻接引理和临界图的结构性质给出了Δ-临界图在△≥6且（Δ-1）度顶点至多邻接一个四度顶点时Fiorini不等式的一个新的下界.
|
| 关 键 词： | 临界图 边染色 第一类图 第二类图 |
A RESULT ON THE NUMBER OF MAJOR VERTEX OF CRITICAL GRAPHS |
| |
| Tian Dadong Zhang Geng Li Mei. A RESULT ON THE NUMBER OF MAJOR VERTEX OF CRITICAL GRAPHS[J]. Journal of Shandong Normal University(Natural Science), 2013, 0(4): 7-9 |
| |
| Authors: | Tian Dadong Zhang Geng Li Mei |
| |
| Affiliation: | Tian Dadong Zhang Geng Li Mei1 ) Qingdao Technological University ( Linyi), 273400, Fei Gounty, Shandong, China 2 ) Sichuan University of Ats and Science ,635000, Dazhou, Sichuan, China ) |
| |
| Abstract: | Let G be a connected graph that is also class two,for any edge e of G,if the edge chromatic number of G／e is strictly less than G,then G is a critical graph.We call a graph is Δ-critical if it is a critical graph with maximum degree Δ.In 1968,Vizing conjectured that the size of a Δ-critical graph of order n is no less than（nΔ-n ＋ 3）/2.Fiorini inequality and discharging method are widely used to prove the above conjecture.By using Vizing Adjacency Lemma and some properties of critical graph,we give a new lower bound to Fiorini inequality for Δ-critical graph when Δ≥6 and every（Δ-1）-vertex in G is adjacent at most one 4-vertex. |
| |
| Keywords: | critical graph edge coloring graph of class one graph of class two |
| 本文献已被 维普 等数据库收录！ |
|
