Every generalized Petersen graph has a Tait coloring

Frank Castagna and Geert Caleb Ernst Prins

Vol. 40 (1972), No. 1, 53–58

DOI: 10.2140/pjm.1972.40.53

Abstract

Watkins has defined a family of graphs which he calls generalized Petersen graphs. He conjectures that all but the original Petersen graph have a Tait coloring, and proves the conjecture for a large number of these graphs. In this paper it is shown that the conjecture is indeed true.

Mathematical Subject Classification 2000

Primary: 05C15

Milestones

Received: 16 June 1970

Revised: 20 August 1970

Published: 1 January 1972