| |
|
|
Abstract: The rainbowness, $\rb(G)$, of a connected plane graph $G$ is the minimum number $k$ such that any colouring of vertices of the graph $G$ using at least $k$ colours involves a face all vertices of which have different colours. For a cubic polyhedral (i.e. 3-connected plane) graph $G$ we prove that $$ \frac n2+\alpha^*_1-1\le \rb(G)\le n-\alpha^*_0+1, $$ where $\alpha^*_0$ and $\alpha^*_1$ denote the independence number and the edge independence number, respectively, of the dual graph $G^*$ of $G$. Moreover, we show that the lower bound is tight and that the upper bound cannot be less than $n-\alpha^*_0$ in general. We also prove that if the dual graph $G^*$ of an $n$-vertex cubic polyhedral graph $G$ has a perfect matching then $$ \rb(G)=\frac34\, n. $$ Contact the authors: jendrol@kosice.upjs.sk Download PDF version of the preprint. |