ICS Theory Group

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)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(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.