A graph and its complement with specified properties. VI. Chromatic and achromatic numbers

Jin Akiyama, Frank Harary and Phillip Arthur Ostrand

Vol. 104 (1983), No. 1, 15–27

DOI: 10.2140/pjm.1983.104.15

Abstract

We characterize the graphs G such that both G and its complement Ḡ are n-colorable, and we specify explicitly all 171 graphs for the case n = 3. We then determine the 41 graphs for which both G and Ḡ have achromatic number 3.

Mathematical Subject Classification 2000

Primary: 05C15

Secondary: 05C75

Milestones

Received: 18 February 1980

Published: 1 January 1983