𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Rainbow faces in edge-colored plane graphs

✍ Scribed by Stanislav Jendrol'; Jozef Miškuf; Roman Soták; Erika Škrabul'áková

Publisher
John Wiley and Sons
Year
2009
Tongue
English
Weight
150 KB
Volume
62
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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

📜 SIMILAR VOLUMES

Edge-face coloring of plane graphs with
Edge-face coloring of plane graphs with maximum degree nine
✍ Jean-Sébastien Sereni; Matěj Stehlík 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 189 KB 👁 1 views

An edge-face coloring of a plane graph with edge set E and face set F is a coloring of the elements of E ∪F so that adjacent or incident elements receive different colors. Borodin [Discrete Math 128(1-3): [21][22][23][24][25][26][27][28][29][30][31][32][33] 1994] proved that every plane graph of max

Facial non-repetitive edge-coloring of p
Facial non-repetitive edge-coloring of plane graphs
✍ Frédéric Havet; Stanislav Jendrol'; Roman Soták; Erika Škrabul'áková 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 124 KB

A sequence r 1 , r 2 , . . . , r 2n such that r i = r n+i for all 1 ≤ i ≤ n is called a repetition. A sequence S is called non-repetitive if no block (i.e. subsequence of consecutive terms of S) is a repetition. Let G be a graph whose edges are colored. A trail is called non-repetitive if the sequen

Alternating cycles in edge-colored graph
Alternating cycles in edge-colored graphs
✍ Carol Whitehead 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 275 KB 👁 1 views

We show that the edges of a 2-connected graph can be partitioned into two color classes so that every vertex is incident with edges of each color and every alternating cycle passes through a single edge. We also show that the edges of a simple graph with minimum vertex degree 6 2 2 can be partitione

Properly colored hamilton cycles in edge
Properly colored hamilton cycles in edge-colored complete graphs
✍ N. Alon; G. Gutin 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 156 KB 👁 3 views

It is shown that, for ⑀ ) 0 and n ) n ⑀ , any complete graph K on n vertices 0 ' Ž . whose edges are colored so that no vertex is incident with more than 1 y 1r 2 y ⑀ n edges of the same color contains a Hamilton cycle in which adjacent edges have distinct colors. Moreover, for every k between 3 and

Simultaneously Colouring the Edges and F
Simultaneously Colouring the Edges and Faces of Plane Graphs
✍ Adrian O. Waller 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 345 KB

In a simultaneous colouring of the edges and faces of a plane graph we colour edges and faces so that every two adjacent or incident pair of them receive different colours. In this paper we prove a conjecture of Mel'nikov which states that for this colouring every plane graph can be coloured with 2+

Edge-face chromatic number and edge chro
Edge-face chromatic number and edge chromatic number of simple plane graphs
✍ Rong Luo; Cun-Quan Zhang 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 201 KB

## Abstract Given a simple plane graph __G__, an edge‐face __k__‐coloring of __G__ is a function ϕ : __E__(__G__) ∪ __F__(G) →  {1,…,__k__} such that, for any two adjacent or incident elements __a__, __b__ ∈ __E__(__G__) ∪ __F__(__G__), ϕ(__a__) ≠ ϕ(__b__). Let χ~e~(__G__), χ~ef~(__G__), and Δ(__G_