Skip to main navigation Skip to search Skip to main content

Uniquely colorable perfect graphs

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

This paper defines the concept of sequential coloring. If G or its complement is one of four major types of perfect graphs, G is shown to be uniquely k-colorable it and only if it is sequentially k-colorable. It is conjectured that this equivalence is true for all perfect graphs. A potential role for sequential coloring in verifying the Strong Perfect Graph Conjecture is discussed. This conjecture is shown to be true for strongly sequentially colorable graphs.

Original languageEnglish
Pages (from-to)187-194
Number of pages8
JournalDiscrete Mathematics
Volume44
Issue number2
DOIs
StatePublished - 1983

Fingerprint

Dive into the research topics of 'Uniquely colorable perfect graphs'. Together they form a unique fingerprint.

Cite this