***** KAIST Discete Math Semianr *****
DATE: February 27, Thursday
TIME: 4PM-5PM
PLACE: E6-1, ROOM 1409
SPEAKER: Seog-Jin Kim (김석진), Konkuk University
TITLE: Injective colorings of graph
http://mathsci.kaist.ac.kr/~sangil/seminar/entry/20090227/
An injective coloring of a graph G is an assignment of colors to the vertices of G so that any two vertices with a common neighbors receives distinct colors. The injective chromatic number, $\chi_i(G)$, is the minimum number of colors needed for an injective coloring. Let $mad(G)$ be the maximum average degree of $G$. In this paper, we show that $\chi_i(G)\leq\Delta + 2$ if $\Delta(G) \geq 4$ and $mad(G) \leq \frac{14}{5}$. When $\Delta(G) = 3$, we show that $mad(G) < \frac{36}{13}$ implies $\chi_i(G) \leq 5$. This is sharp; there is a subcubic graph $H$ such that $mad(H) = \frac{36}{13}$, but $\chi_i(H) = 6$. This is joint work with Daniel Cranston and Gexin Yu.
----------------------------------------------
Informations on future talks can be found at :
http://mathsci.kaist.ac.kr/~sangil/seminar/
Please email to sangil (at) kaist.edu if you wish to receive this
announcements in the future by email.
