𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Vertex signatures and edge-4-colorings of 4-regular plane graphs

✍ Scribed by François Jaeger; Gerhard Koester

Publisher
John Wiley and Sons
Year
1990
Tongue
English
Weight
231 KB
Volume
14
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 of 4‐regular plane graphs made up by the superposition of 4 families of disjoint simple closed curves.

📜 SIMILAR VOLUMES

Almost regular edge colorings and regula
Almost regular edge colorings and regular decompositions of complete graphs
✍ Darryn Bryant; Barbara Maenhaut 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB

## Abstract For __k__ = 1 and __k__ = 2, we prove that the obvious necessary numerical conditions for packing __t__ pairwise edge‐disjoint __k__‐regular subgraphs of specified orders __m__~1~,__m__~2~,… ,__m__~t~ in the complete graph of order __n__ are also sufficient. To do so, we present an edge

Full 4-colorings of 4-regular maps
Full 4-colorings of 4-regular maps
✍ Kenneth A. Berman; H. Shank 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 181 KB 👁 1 views

## Abstract A __full__ coloring of a planar map is a face coloring such that all the faces at ech vertex are colored differently. In this paper the planar 4‐regular maps which have a full 4‐coloring are characterized. This leads to a characterization of the planar maps (not necessarily 4‐valent) wh

3-colorability of 4-regular hamiltonian
3-colorability of 4-regular hamiltonian graphs
✍ Herbert Fleischner; Gert Sabidussi 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 187 KB 👁 1 views

## Abstract On the model of the cycle‐plus‐triangles theorem, we consider the problem of 3‐colorability of those 4‐regular hamiltonian graphs for which the components of the edge‐complement of a given hamiltonian cycle are non‐selfcrossing cycles of constant length ≥ 4. We show that this problem is

Non-rainbow colorings of 3-, 4- and 5-co
Non-rainbow colorings of 3-, 4- and 5-connected plane graphs
✍ Zdeněk Dvořák; Daniel Král'; Riste Škrekovski 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 166 KB 👁 1 views

## Abstract We study vertex‐colorings of plane graphs that do not contain a rainbow face, i.e., a face with vertices of mutually distinct colors. If __G__ is a 3 ‐connected plane graph with __n__ vertices, then the number of colors in such a coloring does not exceed $\lfloor{{7n-8}\over {9}}\rfloo

Dependent edges in Mycielski graphs and
Dependent edges in Mycielski graphs and 4-colorings of 4-skeletons
✍ Karen L. Collins; Kimberly Tysdal 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 174 KB 👁 1 views

## Abstract A dependent edge in an acyclic orientation of a graph is one whose reversal creates a directed cycle. In answer to a question of Erdös, Fisher et al. [5] define __d__~min~(__G__) to be the minimum number of dependent edges of a graph __G__, where the minimum is taken over all acyclic or