Posts Tagged ‘김재훈’

« Older Entries
Newer Entries »

Jaehoon Kim (김재훈), Tree packing conjecture for bounded degree trees

Thursday, December 15th, 2016
Tree packing conjecture for bounded degree trees
Jaehoon Kim (김재훈)
School of Mathematics, Birmingham University, UK
2016/12/28 Wed 4PM-5PM
We prove that if T1,…, Tn is a sequence of bounded degree trees so that Ti has i vertices, then Kn has a decomposition into T1,…, Tn. This shows that the tree packing conjecture of Gyárfás and Lehel from 1976 holds for all bounded degree trees.
We deduce this result from a more general theorem, which yields decompositions of dense quasi-random graphs into suitable families of bounded degree graphs.
In this talk, we discuss the ideas used in the proof.
This is joint work with Felix Joos, Daniela Kühn and Deryk Osthus.

Tags:
Posted in 2016, KAIST Discrete Math Seminar | Comments Closed

1st Korean Workshop on Graph Theory

Tuesday, July 28th, 2015
1st Korean Workshop on Graph Theory
August 26-28, 2015
KAIST  (E6-1 1501 & 3435)
http://home.kias.re.kr/MKG/h/KWGT2015/
  • Program Book
  • Currently, we are planning to have talks in KOREAN.
  • Students/postdocs may get the support for the accommodation. (Hotel Interciti)
  • Others may contact us if you wish to book a hotel at a pre-negotiated price. Please see the website.
  • We may or may not have contributed talks. If you want, please contact us.
  • PLEASE REGISTER UNTIL AUGUST 16.
Location: KAIST
  • Room 1501 of E6-1 (August 26, 27)
  • Room 3435 of E6-1 (August 28)
Invited Speakers:
Organizers:

Tags:, , , , , , , , , , ,
Posted in 2015, KAIST Discrete Math Seminar | Comments Closed

2014 KAIST CMC Discrete Math Workshop

Sunday, November 23rd, 2014
2014 KAIST CMC Discrete Math Workshop
December 10–12, 2014
자연과학동(E6-1), KAIST

Preregistration in kcw2014.eventbrite.com deadline: Dec. 5 (Friday)

ABSTRACTS
Program (Dec.10 Wed-Room 1409)
  • 1:30-2:00 Registration
  • 2:00-2:30 Young Soo Kwon (권영수), Yeungnam University: A variation of list coloring and its properties
  • 2:40-3:10 Mitsugu Hirasaka, Pusan National University: Small topics on association schemes
  • 3:10-3:40 Coffee Break
  • 3:40-4:10 Younjin Kim (김연진),  KAIST: On Extremal Combinatorial Problems of Noga Alon
  • 4:20-4:50 Jang Soo Kim (김장수),  Sungkyunkwan University: A new q-Selberg integral, Schur functions, and Young books
  • 5:00-6:00 Discussion
  • 6:00- Dinner
Program (Dec.11 Thurs-Room 1501 & 3435)
Program (Dec.12 Fri-Room 1501)

Tags:, , , , , , ,
Posted in 2014, KAIST Discrete Math Seminar | Comments Closed

Jaehoon Kim, On r-dynamic coloring of graphs

Wednesday, March 5th, 2014
On r-dynamic coloring of graphs
Jaehoon Kim
KAIST/Univ. of Birmingham, UK
2014/06/09 Monday 4PM-5PM
Room 1409
An r-dynamic proper k-coloring of a graph G is a proper k-coloring of G such that every vertex in V(G) has neighbors in at least \min\{d(v),r\} different color classes. The r-dynamic chromatic number of a graph G, written \chi_r(G), is the least k such that G has such a coloring. By a greedy coloring algorithm, \chi_r(G)\le r\Delta(G)+1 and the equality holds if and only if G is r-regular with diameter 2 and girth 5. We improve the bound to \chi_r(G)\le \Delta(G)+2r when \delta(G)\ge 2r\ln n. In terms of the chromatic number, we prove \chi_r(G)\le r\chi(G) when G is k-regular with k \ge (3+o(1))r\ln r and show that \chi_r(G) may exceed r^{1.377}\chi(G) when k=r. We prove \chi_2(G)\leq \chi(G)+2 when G has diameter 2, with equality only for complete bipartite graphs and the 5-cycle. Also, \chi_2(G)\le 3\chi(G) when G has diameter 3, which is sharp. This is joint work with Sogol Jahanbekam, Suil O, and Douglas B. West.

Tags:
Posted in 2014, KAIST Discrete Math Seminar | Comments Closed

Jaehoon Kim, (0,1)-improper coloring of sparse triangle-free graph

Monday, May 20th, 2013
(0,1)-improper coloring of sparse triangle-free graph
Jaehoon Kim
Department of Mathematics
University of Illinois at Urbana Champagne
2013/06/04 Tuesday 4PM-5PM
ROOM 3433
A graph G is (0,1)-colorable if V(G) can be partitioned into two sets V0 and V1 so that G[V0] is an independent set and G[V1] has maximum degree at most 1. The problem of verifying whether a graph is (0,1)-colorable is NP-complete even in the class of planar graphs of girth 9.

Maximum average degree, Mad(G), is a graph parameter measuring how sparse the graph G is. Borodin and Kostochka showed that every graph G with Mad(G) ≤ 12/5 is (0,1)-colorable, thus every planar graph with girth at least 12 also is (0,1)-colorable.

The aim of this talk is to prove that every triangle-free graph G with Mad(G) ≤ 22/9 is (0,1)-colorable. We prove the slightly stronger statement that every triangle-free graph G with |E(H)| < (11|V(H)|+5)/9 for every subgraph H is (0,1)-colorable and show that there are infinitely many non (0,1)-colorable graphs G with |E(G)|= (11|V(G)|+5)/9.

This is joint work with A. V. Kostochka and Xuding Zhu.

Tags:
Posted in 2013, KAIST Discrete Math Seminar | Comments Closed

« Older Entries
Newer Entries »