Star Coloring and Acyclic Coloring of Locally Planar Graphs
Authors:
- Ken-Ichi KawarabayashiKKKen-Ichi Kawarabayashi
- Bojan MoharBMBojan Mohar
- 1 January 2010
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 24 (1) , 56-71
Abstract
It is proved that every graph embedded in a fixed surface with sufficiently large edge-width is acyclically 7-colorable and that its star chromatic number is at most $2s_0^*+3$, where $s_0^*\leq20$ is the maximum star chromatic number for the class of all planar graphs.
Keywords
This publication has 10 references indexed in Scilit:
- Acyclic colorings of locally planar graphsEuropean Journal of Combinatorics, 2005
- Coloring with no $2$-Colored $P_4$'sThe Electronic Journal of Combinatorics, 2004
- Graphs on Surfaces2001
- Color-Critical Graphs on a Fixed SurfaceJournal of Combinatorial Theory, Series B, 1997
- On acyclic colorings of graphs on surfacesIsrael Journal of Mathematics, 1996
- Graph Coloring Problems1994
- Five-Coloring Maps on SurfacesJournal of Combinatorial Theory, Series B, 1993
- Graph minors. VII. Disjoint paths on a surfaceJournal of Combinatorial Theory, Series B, 1988
- On acyclic colorings of planar graphsDiscrete Mathematics, 1979
- Acyclic colorings of planar graphsIsrael Journal of Mathematics, 1973