✦ LIBER ✦

On-line coloringk-colorable graphs

✍ Scribed by H. A. Kierstead

Publisher: The Hebrew University Magnes Press
Year: 1998
Tongue: English
Weight: 535 KB
Volume: 105
Category: Article
ISSN: 0021-2172
DOI: 10.1007/bf02780324

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

Coloring inductive graphs on-line

✍ Sandy Irani 📂 Article 📅 1994 🏛 Springer 🌐 English ⚖ 895 KB

3D straight-line grid drawing of 4-color

3D straight-line grid drawing of 4-colorable graphs

✍ Tiziana Calamoneri; Andrea Sterbini 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 438 KB

In this paper we contribute to the understanding of the geometric properties of 3D drawings. Namely, we show how to make a 3D straight-line grid drawing of 4-colorable graphs in 0( n\*) volume. Moreover, we prove that each bipartite graph needs at least a( n3/\*) volume. @

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

Parallel and On-Line Graph Coloring

✍ Magnus M Halldórsson 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 209 KB

We discover a surprising connection between graph coloring in two orthogonal paradigms: parallel and on-line computing. We present a randomized on-line Ž . coloring algorithm with a performance ratio of O nrlog n , an improvement of log n factor over the previous best known algorithm of Vishwanathan

On-line coloring of perfect graphs

✍ H. A. Kierstead; K. Kolossa 📂 Article 📅 1996 🏛 Springer-Verlag 🌐 English ⚖ 655 KB