### Schedule

#### 2014-10-13

TimeSpeaker/ Title/ Abstract/ VODLocation
16:30 - 17:30 Improper coloring of planar graphs
Ilkyoo Choi (KASIT),
A graph is $(d_1, \ldots, d_r)$-colorable if its vertex set can be partitioned into $r$ sets $V_1, \ldots, V_r$ where the maximum degree of the graph induced by $V_i$ is at most $d_i$ for each $i\in \{1, \ldots r\}$. For improper coloring of planar graphs with two parts, given $g$ and $d_1$, the question of determining the minimum $d_2=d_2(g, d_1)$ such that planar graphs with girth $g$ are $(d_1, d_2)$-colorable has attracted much interest. The finiteness of $d_2(g, d_1)$ is known for all cases except when $(g, d_1)=(5, 1)$. Montassier and Ochem, as well as Rapaud, asked if $d_2(5, 1)$ is finite. We answer this question in the affirmative with $d_2(5, 1)\leq 10$; namely, we prove that all planar graphs with girth at least $5$ are $(1, 10)$-colorable. Moreover, we prove that for any Euler genus $\gamma$, there exists a $K=K(\gamma)$ where graphs with girth $5$ that are embeddable on a surface of Euler genus $\gamma$ are $(1, K)$-colorable. This is joint work with H. Choi, J. Jeong, and G. Suh.
CAMP seminar room
{"ft_lang_label":"__label__en","ft_lang_prob":0.88450015,"math_prob":0.99934137,"size":1146,"snap":"2019-13-2019-22","text_gpt3_token_len":382,"char_repetition_ratio":0.11383538,"word_repetition_ratio":0.0,"special_character_ratio":0.32897034,"punctuation_ratio":0.15289256,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9997391,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-03-26T10:50:48Z\",\"WARC-Record-ID\":\"<urn:uuid:b373c6d6-3729-4977-9944-c8cda3eec362>\",\"Content-Length\":\"34910\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:2cdeebf4-154c-43f9-80a5-c824fa88ee9e>\",\"WARC-Concurrent-To\":\"<urn:uuid:54f1e55a-b523-4762-aef1-bbc5071173c0>\",\"WARC-IP-Address\":\"210.119.59.13\",\"WARC-Target-URI\":\"https://camp.nims.re.kr/activities/eventpages/?id=208&action=schedule\",\"WARC-Payload-Digest\":\"sha1:OP62JOS5VXXNHVHAPUFPIMJCLSJ56LSL\",\"WARC-Block-Digest\":\"sha1:ZS6IYR6ZLNOO7S54FKDLCZ4AHC2DZ72D\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-13/CC-MAIN-2019-13_segments_1552912204969.39_warc_CC-MAIN-20190326095131-20190326121131-00479.warc.gz\"}"}