Rainbowness of cubic plane graphs (Q856887): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: author (P16): Item:Q582576 |
||
Property / author | |||
Property / author: Stanlislav Jendroľ / rank | |||
Revision as of 11:50, 16 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Rainbowness of cubic plane graphs |
scientific article |
Statements
Rainbowness of cubic plane graphs (English)
0 references
14 December 2006
0 references
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\).
0 references
vertex coloring
0 references
independence number
0 references