Injective colorings of sparse graphs

Details Injective colorings of sparse graphs Injective colorings of sparse graphs

2010-07-05

arxiv.org/abs/1007.0786v1

Discrete Math. Vol. 310, no. 21, 2010, pp. 2965-2973

Mathematics

Combinatorics

10 pages

Scientific paper

Let $mad(G)$ denote the maximum average degree (over all subgraphs) of $G$ and let $\chi_i(G)$ denote the injective chromatic number of $G$. We prove that if $mad(G) \leq 5/2$, then $\chi_i(G)\leq\Delta(G) + 1$; and if $mad(G) < 42/19$, then $\chi_i(G)=\Delta(G)$. Suppose that $G$ is a planar graph with girth $g(G)$ and $\Delta(G)\geq 4$. We prove that if $g(G)\geq 9$, then $\chi_i(G)\leq\Delta(G)+1$; similarly, if $g(G)\geq 13$, then $\chi_i(G)=\Delta(G)$.

Affiliated with

Also associated with

No associations

Rating

Injective colorings of sparse graphs 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 Injective colorings of sparse graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Injective colorings of sparse graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-215710