✦ LIBER ✦

On uniquely 3-colorable graphs

✍ Scribed by Chong-Yun Chao; Zhibo Chen

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 415 KB
Volume: 112
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(93)90220-n

No coin nor oath required. For personal study only.

✦ Synopsis

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 graphs having no subgraph isomorphic to the complete graph K, with k vertices for any integer k>3.

📜 SIMILAR VOLUMES

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

Uniquely colorable perfect graphs

✍ Alan Tucker 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 883 KB

On graphs uniquely colorable under the a

On graphs uniquely colorable under the action of their automorphism groups

✍ G.L. Chia 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 166 KB

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

A characterization of uniquely vertex co

A characterization of uniquely vertex colorable graphs using minimal defining sets

✍ H. Hajiabolhassan; M.L. Mehrabadi; R. Tusserkani; M. Zaker 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 267 KB

A defining set (sf cute-x coloring) of a graph G is a set of vertices S with an assignment of colors to its elements which has a unique completion to a proper coloring of G. We define a minimal d&kg set to be a defining set which does not properly contain another defining set. If G is a uniquely ver

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].