Abstract
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 iff 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.
| Original language | English |
|---|---|
| Pages (from-to) | 136-145 |
| Number of pages | 10 |
| Journal | Journal of Combinatorial Theory, Series B |
| Volume | 63 |
| Issue number | 1 |
| DOIs | |
| State | Published - Jan 1995 |
Fingerprint
Dive into the research topics of 'The signed chromatic number of the projective plane and klein bottle and antipodal graph coloring'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver