Journal of Graph Theory · 2009 · 11 citations · 18 references
Natural SciencesMathematicsCombinatoricsComputational GeometryTopologyGraph AlgorithmsGraph ColoringGraph TheoryEdge ColoringGraph Theory AnalysisInvariantsLower Bounds
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
18
P. Erdös, R. Rado · Journal of the London Mathematical Society · 1950 · 240 citations
Rainbow numbers for matchings and complete graphs
Ingo Schiermeyer · Discrete Mathematics · 2004 · 101 citations
Michael Albert, Alan Frieze, Bruce Reed · The Electronic Journal of Combinatorics · 1995 · 90 citations · Full text
Peter Keevash, Dhruv Mubayi, Benny Sudakov et al. · Combinatorics Probability Computing · 2006 · 78 citations · Full text