𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete

✍ Scribed by David P. Dailey

Publisher
Elsevier Science
Year
1980
Tongue
English
Weight
224 KB
Volume
30
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

It is shown that two sorts of problems belong to the NP-complete clas~;~ First, it is proven that for a given k-colorable graph and a given k-coloring of that graph, determining wbether the graph is or is not uniquely k-colorable is NP-complete. Second, a result by Garey, Johnson, and Stockmeyer is extended with a preof that the coloring of four-regular planar graphs is NP-complete.

📜 SIMILAR VOLUMES

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

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,

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

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

Split and balanced colorings of complete
Split and balanced colorings of complete graphs
✍ Paul Erdös; András Gyárfás 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 429 KB

An (r, n)-split coloring of a complete graph is an edge coloring with r colors under which the vertex set is partitionable into r parts so that for each i, part i does not contain K, in color i. This generalizes the notion of split graphs which correspond to (2, 2)-split colorings. The smallest N fo