Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5777370 | European Journal of Combinatorics | 2017 | 17 Pages |
Abstract
We prove that there exists ϵ,δ>0 such that if G is a 5-critical graph, then |E(G)|â¥(94+ϵ)|V(G)|â54âδT(G) where T(G) is the maximum number of vertex-disjoint cliques of size three or four where cliques of size four have twice the weight of a clique of size three. As a corollary, a triangle-free 5-critical graph G satisfies: |E(G)|â¥(94+ϵ)|V(G)|â54.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Luke Postle,