Citation
S. Fisk et B. Mohar, COLORING GRAPHS WITHOUT SHORT NON-BOUNDING CYCLES, J COMB TH B, 60(2), 1994, pp. 268-276
Citations number
14
Categorie Soggetti
Mathematics, Pure",Mathematics
Journal title
JOURNAL OF COMBINATORIAL THEORY SERIES B
ISSN journal
00958956
→ ACNP
Volume
60
Issue
2
Year of publication
1994
Pages
268 - 276
Database
ISI
SICI code
0095-8956(1994)60:2<268:CGWSNC>2.0.ZU;2-P
Abstract
It is shown that there is a constant c such that if G is a graph embed
ded in a surface of genus g (either orientable or non-orientable) and
the length of a shortest non-bounding cycle of G is at least c log(g 1), then G is six-colorable. A similar result holds for three- and fo
ur-colorings under additional assumptions on the girth of G. (C) 1994
Academic Press, Inc.