Rainbowness of cubic plane graphs (Q856887): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Q5422499 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Colorings of planar graphs with no rainbow faces / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On maximum face-constrained coloring of plane graphs with no short face cycles. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Maximum face-constrained coloring of plane graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Grötzsch's 3-color theorem and its counterparts for the torus and the projective plane / rank | |||
Normal rank |
Latest revision as of 11:36, 25 June 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