Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4657188 | Journal of Combinatorial Theory, Series B | 2012 | 46 Pages |
Abstract
The 1-chromatic number χ1(S)χ1(S) of a surface S is the maximum chromatic number of all graphs which can be drawn on S so that each edge is crossed by no more than one other edge. It is proved that:(a)There is an integer Q>0Q>0 such thatM(Nq)−1⩽χ1(Nq)⩽M(Nq)M(Nq)−1⩽χ1(Nq)⩽M(Nq) for all q⩾Qq⩾Q, where NqNq is the nonorientable surface of genus q and M(Nq)M(Nq) is Ringelʼs upper bound on χ1(Nq)χ1(Nq);(b)χ1(Nq)=M(Nq)χ1(Nq)=M(Nq) for about 7/12 of all nonorientable surfaces NqNq. The results are obtained by using index one current graphs.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Vladimir P. Korzhik,