Premium
Finite fields and the 1‐chromatic number of orientable surfaces
Author(s) -
Korzhik Vladimir P.
Publication year - 2010
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20417
Subject(s) - chromatic scale , mathematics , combinatorics , graph , upper and lower bounds , surface (topology) , enhanced data rates for gsm evolution , discrete mathematics , geometry , mathematical analysis , computer science , artificial intelligence
The 1‐chromatic number χ 1 ( S p ) of the orientable surface S p of genus p is the maximum chromatic number of all graphs which can be drawn on the surface so that each edge is crossed by no more than one other edge. We show that if there exists a finite field of order 4 m +1, m ≥3, then 8 m +2≤χ 1 ( S 4 m 2 − m +1 )≤8 m +3, where 8 m +3 is Ringel's upper bound on χ 1 ( S 4 m 2 − m +1 ). © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 179–184, 2010