Constructing a Family of 4‐Critical Planar Graphs with High Edge Density |
| |
| Authors: | Tianxing Yao Guofei Zhou |
| |
| Institution: | 1. SANJIANG UNIVERSITY, NANJING, CHINA;2. DEPARTMENT OF MATHEMATICS, NANJING UNIVERSITY, NANJING, CHINA |
| |
| Abstract: | A graph  is a k‐critical graph if G is not  ‐colorable but every proper subgraph of G is  ‐colorable. In this article, we construct a family of 4‐critical planar graphs with n vertices and  edges. As a consequence, this improves the bound for the maximum edge density attained by Abbott and Zhou. We conjecture that this is the largest edge density for a 4‐critical planar graph. |
| |
| Keywords: | critical graphs planar graphs |
|
|
is a k‐critical graph if G is not 
‐colorable but every proper subgraph of G is 
‐colorable. In this article, we construct a family of 4‐critical planar graphs with n vertices and 
edges. As a consequence, this improves the bound for the maximum edge density attained by Abbott and Zhou. We conjecture that this is the largest edge density for a 4‐critical planar graph.