边临界图的新下界

数学物理学报

边临界图的新下界

巩在武;吴建良

南京信息工程大学经济与管理学院南京 210044

收稿日期:2004-12-28 修回日期:2006-08-03 出版日期:2008-04-25 发布日期:2008-04-25
通讯作者: 巩在武
基金资助:
国家自然科学基金(70473037)、江苏省社科院项目(院阅B0706)资助

New Lower Bounds for the Number of Edges of Critical Graphs

Gong Zaiwu;Wu Jianliang

College of Economics and Management, Nanjing University of Information Science Technology,Nanjing 210044

Received:2004-12-28 Revised:2006-08-03 Online:2008-04-25 Published:2008-04-25
Contact: Gong Zaiwu

摘要/Abstract

摘要： 图 $G$ 为简单的第二类连通图, 且对 $G$ 的任意边 $e$ ,有 $\chi^{\prime}(G-e)<\chi^{\prime}(G)$ , 则称 $G$ 是临界的.该文给出了阶为 $n$ 边数为 $m$
的 $\Delta$ -临界图的新下界, 即 $m\geq(3\Delta+6)n/10$ , 这里 $1\leq\Delta\leq18$

关键词: 图, 边染色, 临界图

Abstract:

A graph $G$ is critical if it is connected of class two, and $\chi' (G-e)<\chi' (G)$ for any $e$ of $G$ . In this paper, it is proved that any $\Delta$ -critical
graph of order $n$ and size $m$ satisfies: $m\geq(3\Delta+6)n/10$ ,
where $12\leq\Delta\leq18$ .

Key words: Graph, Edge coloring, Critical graph

中图分类号:

05C15

巩在武;吴建良. 边临界图的新下界[J]. 数学物理学报, 2008, 28(2): 367-372.

Gong Zaiwu;Wu Jianliang. New Lower Bounds for the Number of Edges of Critical Graphs[J]. Acta mathematica scientia,Series A, 2008, 28(2): 367-372.

[1]	汪晓艳, 丁义明. 一种去除图像中Cauchy噪声的滤波算法[J]. 数学物理学报, 2018, 38(4): 823-832.
[2]	周军. 一类具有自动催化作用和饱和定律的双分子模型的图灵不稳定性和霍普夫分歧[J]. 数学物理学报, 2017, 37(2): 366-373.
[3]	高黎明. 一类含双参量边值问题的多重解[J]. 数学物理学报, 2015, 35(1): 50-55.
[4]	陈彦恒, 陈贵云. 几乎散在单群的一种刻画[J]. 数学物理学报, 2014, 34(6): 1456-1464.
[5]	王彬. 一类偏向删点及顶点有限制的随机图上的相变[J]. 数学物理学报, 2014, 34(6): 1554-1577.
[6]	蔡东汉, 叶辉. 具有人口转变经济增长模型中的分歧和多重增长路径[J]. 数学物理学报, 2014, 34(1): 9-15.
[7]	张良才, 张苗, 聂文敏. L₁₅(2)}的新刻画[J]. 数学物理学报, 2013, 33(6): 1169-1177.
[8]	庞志峰, 杨余飞, 丁立新, 谢德宣. 解非负约束图像去模糊问题的积极集方法[J]. 数学物理学报, 2013, 33(1): 134-144.
[9]	程东明. 对应于U_q(sl_n)的弱Hopf代数的分类[J]. 数学物理学报, 2012, 32(3): 608-616.
[10]	张亮, 尧小华. 一类带最大单调图的非线性抛物型方程的能控性[J]. 数学物理学报, 2011, 31(5): 1439-1446.
[11]	李增提. 距离正则图相关联的格I[J]. 数学物理学报, 2011, 31(2): 492-499.
[12]	姚兵, 程辉, 姚明, 张忠辅. 图着色下的树顶点邻集的行为[J]. 数学物理学报, 2011, 31(2): 567-576.
[13]	王振宇. 一类链状图的枚举特征——纪念李国平院士吴新谋教授诞辰100周年[J]. 数学物理学报, 2010, 30(5): 1248-1253.
[14]	左连翠, 崔玉泉, 刘家壮. 整数距离图G(D_{m, k,}₂)的点荫度[J]. 数学物理学报, 2010, 30(4): 968-983.
[15]	孔令海, 郇中丹. 灰度图像复原的一种空间适应性向前向后扩散模型[J]. 数学物理学报, 2009, 29(6): 1771-1784.