Title | ||
---|---|---|
The signed chromatic number of the projective plane and Klein bottle and antipodal graph coloring |
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. |
Year | DOI | Venue |
---|---|---|
1995 | 10.1006/jctb.1995.1009 | J. Comb. Theory, Ser. B |
Keywords | Field | DocType |
klein bottle,chromatic number,antipodal graph coloring,projective plane,graph coloring | Real projective plane,Discrete mathematics,Edge coloring,Combinatorics,Signed graph,Fractional coloring,Projective plane,Mathematics,Planar graph,Graph coloring,Complement graph | Journal |
Volume | Issue | ISSN |
63 | 1 | Journal of Combinatorial Theory, Series B |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
1 |
Name | Order | Citations | PageRank |
---|---|---|---|
T. Zaslavsky | 1 | 297 | 56.67 |