Rainbow faces in edge‐colored plane graphs

Stanislav Jendrol′, J. Miškuf, Roman Soták, Erika Škrabuľáková

Journal of Graph Theory · 2009 · 11 citations · 18 references

Concepts

Abstract

Abstract A face of an edge‐colored plane graph is called rainbow if the number of colors used on its edges is equal to its size. The maximum number of colors used in an edge coloring of a connected plane graph G with no rainbow face is called the edge‐rainbowness of G . In this paper we prove that the edge‐rainbowness of G equals the maximum number of edges of a connected bridge face factor H of G , where a bridge face factor H of a plane graph G is a spanning subgraph H of G in which every face is incident with a bridge and the interior of any one face f ∈ F ( G ) is a subset of the interior of some face f ′∈ F ( H ). We also show upper and lower bounds on the edge‐rainbowness of graphs based on edge connectivity, girth of the dual graphs, and other basic graph invariants. Moreover, we present infinite classes of graphs where these equalities are attained. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 84–99, 2009

References

18