On maximum face-constrained coloring of plane graphs with no short face cycles.
type: Item
instance of: scholarly article
title: On maximum face-constrained coloring of plane graphs with no short face cycles.
zbMATH Open document ID: 1034.05023
author: Daniel Král'
published in: Discrete Mathematics
publication date: 2004-03-14T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C65
zbMATH DE Number: 2056551
zbMATH Keywords: planar graph
zbMATH Keywords: planar hypergraph
zbMATH Keywords: coloring
zbMATH Keywords: polychromatic face
reviewed by: Ioan Tomescu
MaRDI profile type: Publication
Wikidata QID: Q57601591
full work available at URL: j.disc.2003.08.001
OpenAlex ID: W2036246085
cites work: On a conjecture of erdöus, simonovits, and sós concerning anti‐Ramsey theorems
cites work: On planar mixed hypergraphs
cites work: Edge-colorings with no large polychromatic stars
cites work: Edge-colorings of complete graphs that avoid polychromatic trees
cites work: On the Erdős–Simonovits–Sós Conjecture about the Anti-Ramsey Number of a Cycle
cites work: Gaps in the chromatic spectrum of face-constrained plane graphs
cites work: Colouring planar mixed hypergraphs
cites work: Coloring face-hypergraphs of graphs on surfaces
cites work: Maximum face-constrained coloring of plane graphs
cites work: On restricted colourings of \(K_ n\)
cites work: Grötzsch's 3-color theorem and its counterparts for the torus and the projective plane
cites work: HYPERGRAPHS
DOI: 10.1016/J.DISC.2003.08.001
description: scientific article; zbMATH DE number 2056551