Abstract
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 Kk with k vertices for any integer k≥3.
Original language | English (US) |
---|---|
Pages (from-to) | 21-27 |
Number of pages | 7 |
Journal | Discrete Mathematics |
Volume | 112 |
Issue number | 1-3 |
DOIs | |
State | Published - Mar 25 1993 |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics