The signed chromatic number of the projective plane and Klein bottle and antipodal graph coloring. (English) Zbl 0822.05028

Zaslavsky, Thomas

J. Comb. Theory, Ser. B 63, No. 1, 136-145 (1995).

A graph with signed edges is \(k\)-colorable if its vertices can be colored from \(\{0, \pm 1, \pm 2,\dots, \pm k\}\) so that the colors of the end- vertices of a positive edge are unequal, and those of a negative edge are not negatives of each other. The author considers signed graphs without positive loops that imbed in the Klein bottle so that a closed walk is orientation-preserving if and only if it has positive sign product. He shows that all such signed graphs are 2-colorable, but not all are 1- colorable—not even when restricting to those that imbed in the projective plane. If color 0 is excluded, then all are 3-colorable, but– -even when restricting to the projective plane—not necessarily 2- colorable.

Reviewer: A.T.White (Kalamazoo)

MSC:

05C15	Coloring of graphs and hypergraphs
05C10	Planar graphs; geometric and topological aspects of graph theory

Keywords:

chromatic number; antipodal graph coloring; signed graphs; Klein bottle; closed walk; projective plane