Rainbowness of cubic plane graphs (Q856887): Difference between revisions

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\).