Article ID Journal Published Year Pages File Type
4657188 Journal of Combinatorial Theory, Series B 2012 46 Pages PDF
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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,