Premium
Constructing a Family of 4‐Critical Planar Graphs with High Edge Density
Author(s) -
Yao Tianxing,
Zhou Guofei
Publication year - 2017
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22123
Subject(s) - combinatorics , mathematics , planar graph , book embedding , conjecture , outerplanar graph , 1 planar graph , graph , discrete mathematics , enhanced data rates for gsm evolution , pathwidth , chordal graph , line graph , computer science , telecommunications
A graph G = ( V , E ) is a k ‐critical graph if G is not ( k − 1 ) ‐colorable but every proper subgraph of G is ( k − 1 ) ‐colorable. In this article, we construct a family of 4‐critical planar graphs with n vertices and7 n − 13 3 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.