Posts Tagged ‘김석진’

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:

Seog-Jin Kim, Bipartite graphs whose squares are not chromatic-choosable

Sunday, August 31st, 2014
Bipartite graphs whose squares are not chromatic-choosable
Seog-Jin Kim
Konkuk University
2014/09/19 *Friday* 4PM-5PM
Room 3433
The square \(G^2\) of a graph \(G\) is the graph defined on \(V(G)\) such that two vertices \(u\) and \(v\) are adjacent in \(G^2\) if the distance between \(u\) and \(v\) in \(G\) is at most 2. Let \(\chi(H)\) and \(\chi_{\ell}(H)\) be the chromatic number and the list chromatic number of \(H\), respectively. A graph \(H\) is called \({chromatic-choosable}\) if \(\chi_{\ell} (H) = \chi(H)\). It is an interesting problem to find graphs that are chromatic-choosable.

Motivated by the List Total Coloring Conjecture, Kostochka and Woodall (2001) proposed the List Square Coloring Conjecture which states that \(G^2\) is chromatic-choosable for every graph \(G\). Recently, Kim and Park showed that the List Square Coloring Conjecture does not hold in general by finding a family of graphs whose squares are complete multipartite graphs with partite sets of unbounded size. It is a well-known fact that the List Total Coloring Conjecture is true if the List Square Coloring Conjecture holds for special class of bipartite graphs. On the other hand, the counterexamples to the List Square Coloring Conjecture are not bipartite graphs. Hence a natural question is whether \(G^2\) is chromatic-choosable or not for every bipartite graph \(G\).

In this paper, we give a bipartite graph \(G\) such that \(\chi_{\ell} (G^2) \neq \chi(G^2)\). Moreover, we show that the value \(\chi_{\ell}(G^2) – \chi(G^2)\) can be arbitrarily large. This is joint work with Boram Park.

Seog-jin Kim (김석진), On-line list colouring of complete multipartite graphs

Wednesday, March 21st, 2012
On-line list colouring of complete multipartite graphs
Seog-Jin Kim (김석진)
Dept. of Mathematics Education, Konkuk University, Seoul, Korea.
2011/4/18 Wed 4PM-5PM
The well-known Ohba Conjecture says that every graph G with |V(G)|≤ 2χ(G)+1 is chromatic choosable.
This paper studies an on-line version of Ohba Conjecture. We prove that unlike the off-line case, for k≥3, the complete multipartite graph K2*(k-1), 3 is not on-line chromatic-choosable. Based on this result, the on-line version of Ohba Conjecture is modified as follows: Every graph G with |V(G)|≥ 2χ(G) is on-line chromatic choosable. We present an explicit strategy to show that for any positive integer k, the graph K2*k is on-line chromatic-choosable. We then present a minimal function g for which the graph K2*(k-1), 3 is on-line g-choosable. This is joint work with Young Soo Kwon, Daphne Der-Fen Liu, and Xuding Zhu.

Seog-Jin Kim (김석진), Decomposition of Sparse Graphs into Forests and a Graph with Bounded Degree

Thursday, March 3rd, 2011
Decomposition of Sparse Graphs into Forests and a Graph with Bounded Degree
Seog-Jin Kim (김석진)
Dept. of Mathematics Education, Konkuk University, Seoul, Korea.
2011/3/10 Thu 5PM-6PM
Say that a graph with maximum degree at most d is d-bounded. For d>k, we prove a sharp sparseness condition for decomposability into k forests and a d-bounded graph. Consequences ar e that every graph with fractional arboricity at most k+ d/(k+d+1) has such a decomposition, and (for k=1) every graph with maximum average degree less than 2+2d/(d+2) decomposes into a forest and a d-bounded graph. When d=k+1, and when k=1 and d≤6, the d-bounded graph in the decomposition can also be required to be a forest. When k=1 and d≤2, the d-bounded forest can also be required to have at most d edges in each component.
This is joint work with A.V. Kostochka, D.B. West, H. Wu, and X. Zhu.

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

Thursday, February 12th, 2009
Injective colorings of graphs with low average degree
Seog-Jin Kim (김석진)
Dept. of Mathematics Education, Konkuk University, Seoul, Korea.
2009/02/27 Fri, 4PM-5PM 3PM-4PM
An injective coloring of a graph G is an assignment of colors to the vertices of G so that any two vertices with a common neighbors receives distinct colors. The injective chromatic number, \(\chi_i(G)\), is the minimum number of colors needed for an injective coloring. Let \(mad(G)\) be the maximum average degree of G. In this paper, we show that \(\chi_i(G)\leq\Delta + 2\) if \(\Delta(G) \geq 4\) and \(mad(G) \leq \frac{14}{5}\). When \(\Delta(G) = 3\), we show that \(\)mad(G) < \frac{36}{13}[/latex] implies [latex]\chi_i(G) \leq 5[/latex]. This is sharp; there is a subcubic graph [latex]H[/latex] such that [latex]mad(H) = \frac{36}{13}[/latex], but [latex]\chi_i(H) = 6[/latex]. This is joint work with Daniel Cranston and Gexin Yu.