Acta mathematica scientia,Series A

• Articles • Previous Articles     Next Articles

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

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

CLC Number: 

  • 05C15
Trendmd