Every generalized Petersen graph has a Tait coloring
Frank Castagna, Geert Prins · Pacific Journal of Mathematics · 1972
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. DEFINITIONS.Let n and k be positive integers, k ^ n -1, n Φ 2k.The generalized Petersen graph G(n, k) has 2n vertices, denoted by {0, 1, 2, , n -1; 0', Γ, 2', , , (n -1)'} and all edges of the form (ΐ, ί + 1), (i, i'), (ί', (i + k) f ) for 0 ^ i ^ n -1, where all numbers are read modulo n.G(5, 2) is the Petersen graph.See Watkins [2].The sets of edges {(i, i + 1)} and {(i', (i + k) f )} are called the outer and inner rims respectively and the edges (£, i') are called the spokes.A Tait coloring of a trivalent graph is an edge-coloring in three colors such that each color is incident to each vertex.A 2-factor of a graph is a bivalent spanning subgraph.A 2-factor consists of disjoint circuits.A Tait cycle of a trivalent graph is a 2~factor all of whose circuits have even length.A Tait cycle induces a Tait coloring and conversely.The method that Watkins used in proving that many generalized Petersen graphs have a Tait coloring was to prove that certain color patterns on the spokes induce a Tait coloring.Our method for the remaining cases consists of the construction of 2-factors and of proof that these 2-factors are Tait cycles under appropriate conditions.We restrict ourselves to the generalized Petersen graphs G(n, k) with the properties: