Injective colorings of graphs with low average degree

Details Injective colorings of graphs with low average degree Injective colorings of graphs with low average degree

2010-06-18

arxiv.org/abs/1006.3776v1

Algorithmica. Vol. 60(3), 2011, pp. 553-568

Mathematics

Combinatorics

15 pages, 3 figures

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 $\Delta\geq 4$ and $\mad(G)<\frac{14}5$, then $\chi_i(G)\leq\Delta+2$. When $\Delta=3$, we show that $\mad(G)<\frac{36}{13}$ implies $\chi_i(G)\le 5$. In contrast, we give a graph $G$ with $\Delta=3$, $\mad(G)=\frac{36}{13}$, and $\chi_i(G)=6$.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-261323