A graph with signed edges (a signed graph) is k-colorable if its vertices can be colored using only the colors 0, +/-1,...,+/-k so that the colors of the endpoints of a positive edge are unequal while those of a negative edge are not negatives of each other. Consider the signed graphs without positive loops that embed in the Klein bottle so that a closed walk preserves orientation ilf its sign product is positive. All of them are 2-colorable but not all are 1-colorable, not even if one restricts to the signed graphs that embed in the projective plane. If the color 0 is excluded, all are 3-colorable but, even restricting to the projective plane, not necessarily 2-colorable. (C) 1995 Academic Press, Inc. [References: 8]
展开▼
