## Posts Tagged ‘김석진’

### Seog-Jin Kim (김석진), Injective colorings of graphs with low average degree

Thursday, February 12th, 2009
Injective colorings of graphs with low average degree
Seog-Jin Kim (김석진)
Dept. of Mathematics Education, Konkuk University, Seoul, Korea.
2009/02/27 Fri, 4PM-5PM 3PM-4PM
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}[/latex] 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.

### Seog-Jin Kim (김석진), List-coloring the Square of a Subcubic Graph

Friday, August 22nd, 2008
List-coloring the Square of a Subcubic Graph
Seog-Jin Kim (김석진)
Dept. of Mathematics Education, Konkuk University, Seoul, Korea.
2008/05/01 Thu, 3PM-4PM

The square G2 of a graph G is the graph with the same vertex set as G and with two vertices adjacent if their distance in G is at most 2. Thomassen showed that for a planar graph G with maximum degree Δ(G)=3 we have χ(G2)≤7. Kostochka and Woodall conjectured that for every graph, the list-chromatic number of G2 equals the chromatic number of G2, that is χl(G2)=χ(G2) for all G. If true, this conjecture (together with Thomassen’s result) implies that every planar graph G with Δ(G)=3 satisfies χl(G2)≤7. We prove that every graph (not necessarily planar) with Δ(G)=3 other than the Petersen graph satisfies χl(G2)≤8 (and this is best possible). In addition, we show that if G is a planar graph with Δ(G)=3 and girth g(G)≥7, then χl(G2)≤7. Dvořák, Škrekovski, and Tancer showed that if G is a planar graph with Δ(G)=3 and girth g(G)≥10, then χl(G2)≤6. We improve the girth bound to show that: if G is a planar graph with Δ(G)=3 and g(G)≥9, then χl(G2)≤6. This is joint work with Daniel Cranston.