
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\).
Coloring of graphs and hypergraphs, vertex coloring, Discrete Mathematics and Combinatorics, Three-dimensional polytopes, independence number, Theoretical Computer Science
Coloring of graphs and hypergraphs, vertex coloring, Discrete Mathematics and Combinatorics, Three-dimensional polytopes, independence number, Theoretical Computer Science
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 8 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
