✦ LIBER ✦

Uniquely Edge-3-Colorable Graphs and Snarks

✍ Scribed by John L. Goldwasser; Cun-Quan Zhang

Publisher: Springer Japan
Year: 2000
Tongue: English
Weight: 164 KB
Volume: 16
Category: Article
ISSN: 0911-0119
DOI: 10.1007/pl00007221

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On uniquely 3-colorable graphs

✍ Chong-Yun Chao; Zhibo Chen 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 415 KB

We show the following. (1) For each integer n> 12, there exists a uniquely 3-colorable graph with n vertices and without any triangles. (2) There exist infinitely many uniquely 3-colorable regular graphs without any triangles. It follows that there exist infinitely many uniquely k-colorable regular

On uniquely 3-colorable graphs II

✍ Chong-Yun Chao; Zhibo Chen 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 428 KB

In [2], for each non-negative integer k, we constructed a connected graph with (24)2k vertices which is uniquely 3-colorable, regular with degree k+5, and triangle-free. Here, for each positive integer n and each integer r > 5, we construct a connected graph with (26)n .2'-' vertices which is unique

Cubic graphs with three Hamiltonian cycl

Cubic graphs with three Hamiltonian cycles are not always uniquely edge colorable

✍ Andrew Thomason 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 138 KB 👁 1 views

## Abstract The generalized Petersen graph __P__(6__k__ + 3, 2) has exactly 3 Hamiltonian cycles for __k__ ≥ 0, but for __k__ ≥ 2 is not uniquely edge colorable. This disproves a conjecture of Greenwell and Kronk [1].

Hamiltonian weights and unique 3-edge-co

Hamiltonian weights and unique 3-edge-colorings of cubic graphs

✍ Cun-Quan Zhang 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 402 KB

## Abstract A (1,2)‐eulerian weight __w__ of a grph is hamiltonian if every faithful cover of __w__ is a set of two Hamilton circuits. Let __G__ be a 3‐connected cubic graph containing no subdivition of the Petersen graph. We prove that if __G__ admits a hamiltonian weight then __G__ is uniquely 3‐

Kr-Free Uniquely Vertex Colorable Graphs

Kr-Free Uniquely Vertex Colorable Graphs with Minimum Possible Edges

✍ S. Akbari; V.S. Mirrokni; B.S. Sadjad 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 112 KB

We construct counterexamples to the conjecture of Xu (1990, J. Combin. Theory Ser. B 50, 319 320) that every uniquely r-colorable graph of order n with exactly (r&1) n&( r2 ) edges must contain a K r . ## 2001 Academic Press Harary et al. [4] constructed uniquely r-colorable graphs containing no

Maximum Δ-edge-colorable subgraphs of cl

Maximum Δ-edge-colorable subgraphs of class II graphs

✍ Vahan V. Mkrtchyan; Eckhard Steffen 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 180 KB

## Abstract A graph __G__ is class II, if its chromatic index is at least Δ + 1. Let __H__ be a maximum Δ‐edge‐colorable subgraph of __G__. The paper proves best possible lower bounds for |__E__(__H__)|/|__E__(__G__)|, and structural properties of maximum Δ‐edge‐colorable subgraphs. It is shown tha