𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On uniquely partitionable planar graphs

✍ Scribed by Peter Mihók; Jozef Bucko; Margit Voigt

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
444 KB
Volume
191
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Let ~1,22 ..... ~,; n/>2 be any properties of graphs. A vertex (~L, ~2 ..... J~,,)-partition of a graph G is a partition (V1, l~,...,/7,,) of V(G) such that for each i = 1,2 ..... n the induced subgraph G[Vi] has the property ~i. A graph G is said to be uniquely (~1,~2 ..... ~,)-partitionable if G has unique vertex (2~1, ~2,..., ~,)-partition. In the present paper we investigate the problem of the existence of uniquely (~1,~2 .... , ~n)-partitionable planar graphs for additive and hereditary properties ~1, ~2,..., ~, of graphs. Some constructions and open problems are presented for n = 2. (~

📜 SIMILAR VOLUMES

On uniquely 3-colorable graphs
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
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

On the circular chromatic number of circ
On the circular chromatic number of circular partitionable graphs
✍ Arnaud Pêcher; Xuding Zhu 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 168 KB

## Abstract This article studies the circular chromatic number of a class of circular partitionable graphs. We prove that an infinite family of circular partitionable graphs __G__ has $\chi\_ c (G) = \chi(G)$. A consequence of this result is that we obtain an infinite family of graphs __G__ with th

Unique and faithful embeddings of projec
Unique and faithful embeddings of projective-planar graphs
✍ Seiya Negami 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 393 KB

A graph G is uniquelyembeddable in a surface f 2 if for any two embeddings f,,f2 : G + f 2 , there exists an isomorphism u : G + G and a homeo- admits an embedding f : G + F2 such that for any isomorphism (T : G + G, there is a homeomorphism h : F 2 f 2 with h . f = f . u. It will be shown that if

On planar hypohamiltonian graphs
On planar hypohamiltonian graphs
✍ Gábor Wiener; Makoto Araya 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 144 KB

We present a planar hypohamiltonian graph on 42 vertices and (as a corollary) a planar hypotraceable graph on 162 vertices, improving the bounds of Zamfirescu and Zamfirescu and show some other consequences. We also settle the open problem whether there exists a positive integer N, such that for eve