Degenerate and star colorings of graphs on surfaces

Details Degenerate and star colorings of graphs on surfaces Degenerate and star colorings of graphs on surfaces

2008-06-06

arxiv.org/abs/0806.1242v1

Mathematics

Combinatorics

16 pages, 2 figures

Scientific paper

We study the degenerate, the star and the degenerate star chromatic numbers and their relation to the genus of graphs. As a tool we prove the following strengthening of a result of Fertin et al.: If $G$ is a graph of maximum degree $\Delta$, then $G$ admits a degenerate star coloring using $O(\Delta^{3/2})$ colors. We use this result to prove that every graph of genus $g$ admits a degenerate star coloring with $O(g^{3/5})$ colors. It is also shown that these results are sharp up to a logarithmic factor.

Affiliated with

Also associated with

No associations

Rating

Degenerate and star colorings of graphs on surfaces does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Degenerate and star colorings of graphs on surfaces, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Degenerate and star colorings of graphs on surfaces will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-11535