On uniquely 3-colorable graphs

Chong Yun Chao, Zhibo Chen

Research output: Contribution to journalArticlepeer-review

15 Scopus citations

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 languageEnglish (US)
Pages (from-to)21-27
Number of pages7
JournalDiscrete Mathematics
Volume112
Issue number1-3
DOIs
StatePublished - Mar 25 1993

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'On uniquely 3-colorable graphs'. Together they form a unique fingerprint.

Cite this