数学物理学报

• 论文 • 上一篇    下一篇

边临界图的新下界

巩在武;吴建良   

  1. 南京信息工程大学经济与管理学院 南京 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   

  1. 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

摘要: G 为简单的第二类连通图, 且对G 的任意边e,有χ(Ge)<χ(G), 则称 G是临界的.该文给出了阶为n 边数为m
Δ -临界图的新下界, 即m(3Δ+6)n/10, 这里1Δ18

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

Abstract:

A graph G is critical if it is connected of class two, and χ(Ge)<χ(G) for any e of G. In this paper, it is proved that any Δ-critical
graph of order n and size m satisfies: m(3Δ+6)n/10,
where 12Δ18.

Key words: Graph, Edge coloring, Critical graph

中图分类号: 

  • 05C15