Discrete Math Seminar (김석진)

상일 2008.04.14 05:13 조회 수 : 2972

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

댓글 0

번호 제목 글쓴이 날짜 조회 수
204 응용수학 세미나(수,4:30, 최정민박사) 과사무실 2008.04.30 2028
203 대수구조 및 응용연구센터 세미나(변동호) 과사무실 2008.04.30 2764
202 학부생 콜로키움 제3회 (진교택 교수) [1] 과사무실 2008.04.29 1350
201 Stochastic Calculus 집중강연 BK사업단 2008.04.28 1129
200 수리과학과 Colloquium(4/25(금),16:00) 과사무실 2008.04.19 1133
199 대수구조 및 응용연구센터 세미나 (강순이) 과사무실 2008.04.15 2562
198 Function Theory Seminar 과사무실 2008.04.14 1413
197 Discrete Math Seminar (Roy Meshulam) 상일 2008.04.14 2843
» Discrete Math Seminar (김석진) 상일 2008.04.14 2972
195 응용수학 세미나(수,4:30, 이영수박사) 과사무실 2008.04.12 1550
194 응용수학 세미나(수,4:00, 황형주교수) 과사무실 2008.04.12 3039
193 응용수학 세미나(수,5:00, 조은주박사) 과사무실 2008.04.12 1556
192 학부생 콜로퀴엄 제4회 (강석진 교수) 과사무실 2008.04.11 2058
191 수리과학과 Colloquium(4/11(금),16:00) 과사무실 2008.04.05 1169
190 김도윤박사 세미나(4/4(금)16:00) 과사무실 2008.04.04 2852
189 응용수학세미나 (수,4:30,김종민박사) 과사무실 2008.03.21 2951
188 Game Theory 세미나 (김정유교수,3.25(화)17:30) 과사무실 2008.03.19 3003
187 Game Theory 세미나 (김정유교수,3.18(화)17:30) BK사업단 2008.03.18 2105
186 응용수학세미나 (금,4:30,임지선박사) 과사무실 2008.03.15 2973
185 응용수학세미나 (수,4:30,김용정) 과사무실 2008.03.13 1235