|
|||||
|
|
On the edge-density of 4-critical graphs |
|
| Authors: | Babak Farzad Michael Molloy |
| Affiliation: | (1) Cheriton School of Computer Science, University of Waterloo, Waterloo, Canada;(2) Department of Computer Science, University of British Columbia, Vancouver, Canada;(3) Department of Computer Science, Concordia University, Montreal, Canada |
| Abstract: | Gallai conjectured that every 4-critical graph on n vertices has at least 5/3n-2/3 edges. We prove this conjecture for 4-critical graphs in which the subgraph induced by vertices of degree 3 is connected. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |