# ICS 269, Fall 1998: Theory Seminar

## December 4, 1998:

On Uniquely 3-colorable Graphs II [*]

presented by David Goggin, ICS, UC Irvine

In [**], for each non-negative integer *k*,
we constructed a connected graph with
(24)2^{k} 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^{(r-5)} vertices
which is uniquely 3-colorable, regular with degree *r*,
and triangle-free.

*References:*

[*] Chong-Yun Chao, Zhibo Chen.
On Uniquely 3-colorable Graphs II,
Discrete Mathematics, July '98, 259-265.

[**] C.-Y. Chao, Z. Chen. On Uniquely 3-colorable Graphs, Discrete Math.
112 (1993) 21-27.