pith. machine review for the scientific record. sign in

arxiv: 1006.3776 · v1 · submitted 2010-06-18 · 🧮 math.CO · cs.DM

Recognition: unknown

Injective colorings of graphs with low average degree

Authors on Pith no claims yet
classification 🧮 math.CO cs.DM
keywords deltafracaveragedegreedenoteinjectivechromaticcolorings
0
0 comments X
read the original abstract

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$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.