On maximum face-constrained coloring of plane graphs with no short face cycles. (Q1426126): Difference between revisions
From MaRDI portal
Set profile property. |
Created claim: Wikidata QID (P12): Q57601591, #quickstatements; #temporary_batch_1709751086066 |
||
Property / Wikidata QID | |||
Property / Wikidata QID: Q57601591 / rank | |||
Normal rank |
Revision as of 21:07, 6 March 2024
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
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
planar graph
0 references
planar hypergraph
0 references
coloring
0 references
polychromatic face
0 references