Rainbowness of cubic plane graphs
type: Item
instance of: scholarly article
title: Rainbowness of cubic plane graphs
zbMATH Open document ID: 1109.05044
published in: Discrete Mathematics
publication date: 2006-12-14T00:00:00Z
review text: Given a plane graph \(G\), the rainbowness \(\mathrm{rb}(G)\) of \(G\) is the smallest integer \(k\) such that any (not necessarily proper) coloring of the vertices of \(G\) with \(k\) colors involves a face all vertices of which receive distinct colors. The author proves that, for any \(n\)-vertex connected cubic plane graph \(G\), \(\frac{n}{2}+\alpha_1(G^*)-1\leq \mathrm{rb}(G)\leq n-\alpha_0(G^*)+1\), where \(G^*\) is the dual graph of \(G\), \(\alpha_0\) and \(\alpha_1\) denote the independence number and the edge independence number, respectively. The bounds are tight. The author conjectures that, for any \(n\)-vertex \(3\)-connected cubic plane graph \(G\), we have \(\mathrm{rb}(G)= \frac{n}{2}+\alpha_1(G^*)-1\).
reviewed by: Van Bang Le
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 52B10
zbMATH DE Number: 5080076
zbMATH Keywords: vertex coloring
zbMATH Keywords: independence number
author: Stanislav Jendroľ
MaRDI profile type: Publication
full work available at URL: j.disc.2006.06.012
OpenAlex ID: W1977852522
cites work: Q5422499
cites work: Colorings of planar graphs with no rainbow faces
cites work: On maximum face-constrained coloring of plane graphs with no short face cycles.
cites work: Maximum face-constrained coloring of plane graphs
cites work: Grötzsch's 3-color theorem and its counterparts for the torus and the projective plane
DOI: 10.1016/J.DISC.2006.06.012
Recommended article: Rainbowness of plane graphs
Recommended article: Rainbow cycles in cube graphs
Recommended article: Q3015647
Recommended article: Q5741008
Recommended article: Saturated rainbow edge colorings of cube graphs
Recommended article: Rainbow faces in edge‐colored plane graphs
Recommended article: Vertex rainbow colorings of graphs
Recommended article: Rainbow tetrahedra in Cayley graphs
Recommended article: Facial rainbow coloring of plane graphs
Recommended article: Q2939155
description: scientific article; zbMATH DE number 5080076