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
    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
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references