***** KAIST Discete Math Semianr *****
DATE: May 1st, Thursday
TIME: 3PM-4PM
PLACE: E6-1, ROOM 1409
SPEAKER: Seog-Jin Kim(김석진), Konkuk University
TITLE: List-coloring the Square of a Subcubic Graph
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.
----------------------------------------------
Informations on future talks can be found at :
http://math.kaist.ac.kr/~sangil/seminar.php
Please email to sangil (at) kaist.edu if you wish to receive this
announcements in the future by email.