𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Simultaneous coloring of edges and faces of plane graphs

✍ Scribed by Oleg V. Borodin

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
888 KB
Volume
128
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

The edges and faces of a plane graph are colored so that every two adjacent or incident of them are colored differently. The minimal number of colors for this kind of coloring is estimated. For the plane graphs of the maximal degree at least 10, the bound is the best possible. The proof is based on some new generalizations of Kotzig's Theorem on the minimal weight of edges in plane graphs. Another tool is the concept of assigned coloring (choosability).

📜 SIMILAR VOLUMES

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+

Rainbow faces in edge-colored plane grap
Rainbow faces in edge-colored plane graphs
✍ Stanislav Jendrol'; Jozef Miškuf; Roman Soták; Erika Škrabul'áková 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 150 KB

## 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 pap

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

A six-color theorem for the edge-face co
A six-color theorem for the edge-face coloring of plane graphs
✍ Cuiqin Lin; Guanzhang Hu; Zhongfu Zhang 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 218 KB

It was shown (Kronk and Mitchen, 1973) that the set of vertices, edges and faces of any normal map on the sphere can be colored with seven colors. In this paper we solve a somewhat different problem: the set of edges and faces of any plane graph with A ~< 3 can be colored by six colors.

Coloring edges of embedded graphs
Coloring edges of embedded graphs
✍ Daniel P. Sanders; Yue Zhao 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 80 KB 👁 2 views

In this paper, we prove that any graph G with maximum degree ÁG ! 11 p 49À241AEa2, which is embeddable in a surface AE of characteristic 1AE 1 and satis®es jVGj b 2ÁGÀ5À2 p 6ÁG, is class one.

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