Large faces in 4-critical planar graphs with minimum degree 4 (Q1906842)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Large faces in 4-critical planar graphs with minimum degree 4 |
scientific article |
Statements
Large faces in 4-critical planar graphs with minimum degree 4 (English)
0 references
18 June 1996
0 references
A graph \(G\) is said to be \(k\)-critical if it has chromatic number \(k\), but every proper subgraph of \(G\) has a \((k- 1)\)-coloring. Let \(\mathcal G\) be the class of 4-critical planar graphs with minimal degree \(\delta\geq 4\). The main result of this paper is the following: Let \(G= (V, E)\in {\mathcal G}\). Then no face of \(G\) has more than \({1\over 2}|V|\) vertices. Also there exist absolute constants \(c_1\) and \(c_2\) such that for all \(n\geq c_1\) there exists a graph \(G\) in \(\mathcal G\) of order \(n\) whose largest face has size at least \({n\over 2}- c_2\).
0 references
chromatic number
0 references
4-critical planar graphs
0 references
largest face
0 references