Skip to main navigation Skip to search Skip to main content

The signed chromatic number of the projective plane and klein bottle and antipodal graph coloring

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

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 languageEnglish
Pages (from-to)136-145
Number of pages10
JournalJournal of Combinatorial Theory, Series B
Volume63
Issue number1
DOIs
StatePublished - 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