Premium
Rainbow faces in edge‐colored plane graphs
Author(s) -
Jendrol' Stanislav,
Miškuf Jozef,
Soták Roman,
Škrabul'áková Erika
Publication year - 2009
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20382
Subject(s) - combinatorics , rainbow , mathematics , edge coloring , discrete mathematics , plane (geometry) , graph , enhanced data rates for gsm evolution , graph power , line graph , geometry , computer science , physics , artificial intelligence , optics
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