Dept. of Mathematics Education, Konkuk University, Seoul, Korea.

## Posts Tagged ‘김석진’

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

Thursday, February 12th, 2009Dept. of Mathematics Education, Konkuk University, Seoul, Korea.

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

Friday, August 22nd, 2008Dept. of Mathematics Education, Konkuk University, Seoul, Korea.

The *square* G^{2} 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 χ(G^{2})≤7. Kostochka and Woodall conjectured that for every graph, the list-chromatic number of G^{2} equals the chromatic number of G^{2}, that is χ_{l}(G^{2})=χ(G^{2}) for all G. If true, this conjecture (together with Thomassen’s result) implies that every planar graph G with Δ(G)=3 satisfies χ_{l}(G^{2})≤7. We prove that every graph (not necessarily planar) with Δ(G)=3 other than the Petersen graph satisfies χ_{l}(G^{2})≤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}(G^{2})≤7. Dvořák, Škrekovski, and Tancer showed that if G is a planar graph with Δ(G)=3 and girth g(G)≥10, then χ_{l}(G^{2})≤6. We improve the girth bound to show that: if G is a planar graph with Δ(G)=3 and g(G)≥9, then χ_{l}(G^{2})≤6. This is joint work with Daniel Cranston.