On maximum face-constrained coloring of plane graphs with no short face cycles. (Q1426126)

From MaRDI portal
scientific article
Language Label Description Also known as
English
On maximum face-constrained coloring of plane graphs with no short face cycles.
scientific article

    Statements

    On maximum face-constrained coloring of plane graphs with no short face cycles. (English)
    0 references
    0 references
    14 March 2004
    0 references
    A face of a plane graph is said to be polychromatic if all its vertices receive mutually different colors. In this paper it is shown that the vertices of each plane graph \(G\) of order \(n\) can be colored in such a way that \(G\) does not contain a polychromatic face using at least: \(n-m\) colors if the dual graph \(G^{*}\) of \(G\) has a covering with \(m\) edges; \(\lceil n/2\rceil +1\) if all face cycles have lengths at least five and \(n\geq 4\); \(\lceil (g^{2}-g-8)n/(g^{2}+g-6)+(4g+4)/(g^{2}+g-6)\rceil \) if all face cycles have lengths at least \(g\), \(g\geq 5\) and \(n\geq (g+3)/2\).
    0 references
    0 references
    0 references
    0 references
    0 references
    planar graph
    0 references
    planar hypergraph
    0 references
    coloring
    0 references
    polychromatic face
    0 references
    0 references
    0 references
    0 references