𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Simultaneously Colouring the Edges and Faces of Plane Graphs

✍ Scribed by Adrian O. Waller

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
345 KB
Volume
69
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

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+3 colours, where 2 is the maximum degree of a vertex in the graph.

📜 SIMILAR VOLUMES

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_

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

Vertex signatures and edge-4-colorings o
Vertex signatures and edge-4-colorings of 4-regular plane graphs
✍ François Jaeger; Gerhard Koester 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 231 KB 👁 1 views

## Abstract We associate partitions of the edge‐set of a 4‐regular plane graph into 1‐factors or 2‐factors to certain 3‐valued vertex signatures in the spirit of the work by H. Grötzsch [1]. As a corollary we obtain a simple proof of a result of F. Jaeger and H. Shank [2] on the edge‐4‐colorability

The plane-width of graphs
The plane-width of graphs
✍ Marcin Kamiński; Paul Medvedev; Martin Milanič 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 192 KB

Map the vertices of a graph to (not necessarily distinct) points of the plane so that two adjacent vertices are mapped at least unit distance apart. The plane-width of a graph is the minimum diameter of the image of its vertex set over all such mappings. We establish a relation between the plane-wid

A list version of Dirac's theorem on the
A list version of Dirac's theorem on the number of edges in colour-critical graphs
✍ Alexandr V. Kostochka; Michael Stiebitz 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 110 KB 👁 2 views

## Abstract One of the basic results in graph colouring is Brooks' theorem [R. L. Brooks, Proc Cambridge Phil Soc 37 (1941) 194–197], which asserts that the chromatic number of every connected graph, that is not a complete graph or an odd cycle, does not exceed its maximum degree. As an extension o