Constructing a Family of 4-Critical Planar Graphs with High Edge-Density

Yao Tianxing, Zhou Guofei

A graph $G=(V,E)$ is a $k$-critical graph if $G$ is not $(k-1)$-colorable but $G-e$ is $(k-1)$-colorable for every $e\in E(G)$. In this paper, we construct a family of 4-critical…