✦ LIBER ✦

Structure of neighborhoods of edges in planar graphs and simultaneous coloring of vertices, edges and faces

✍ Scribed by O. V. Borodin

Publisher: SP MAIK Nauka/Interperiodica
Year: 1993
Tongue: English
Weight: 667 KB
Volume: 53
Category: Article
ISSN: 0001-4346
DOI: 10.1007/bf01208542

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Simultaneous coloring of edges and faces

Simultaneous coloring of edges and faces of plane graphs

✍ Oleg V. Borodin 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 888 KB

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

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.

Orbits on vertices and edges of finite g

Orbits on vertices and edges of finite graphs

✍ Dominique Buset 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 134 KB

Given two integers v > 0 and e/> 0, we prove that there exists a finite graph (resp. a finite connected graph) whose automorphism group has exactly v orbits on the set of vertices and e orbits on the set of edges if and only if v ~< 2e + 1 (resp. v ~< e + 1).

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+

NP-completeness of list coloring and pre

NP-completeness of list coloring and precoloring extension on the edges of planar graphs

✍ Dániel Marx 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 110 KB

## Abstract In the edge precoloring extension problem, we are given a graph with some of the edges having preassigned colors and it has to be decided whether this coloring can be extended to a proper __k__‐edge‐coloring of the graph. In list edge coloring every edge has a list of admissible colors,

Edges and Kuratowski Subgraphs of Non-Pl

Edges and Kuratowski Subgraphs of Non-Planar Graphs

✍ Jozef Širáň 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 225 KB

It is proved that any edge of a Pconnected non-planar graph G of order a t least 6 lies in a subdivision of K3,3 in G. For any 3-connected non-planar graph G of order a t least 6 we show that G contains at most four edges which belong to no subdivisions of K3,3 in G.