## Posts Tagged ‘김석진’

### Seog-Jin Kim (김석진), Signed coloring and list coloring of k-chromatic graphs

Wednesday, January 2nd, 2019

IBS/KAIST Joint Discrete Math Seminar

Signed colouring and list colouring of k-chromatic graphs
Seog-Jin Kim (김석진)
Department of Mathematics Education, Konkuk University, Seoul
2019/1/28 Mon 4PM-5PM (Room B232, IBS)
A signed graph is a pair (G, σ), where G is a graph and σ: E(G) → {1,-1} is a signature of G. A set S of integers is symmetric if I∈S implies that -i∈S. A k-colouring of (G,σ) is a mapping f:V(G) → Nk such that for each edge e=uv, f(x)≠σ(e) f(y), where Nk is a symmetric integer set of size k. We define the signed chromatic number of a graph G to be the minimum integer k such that for any signature σ of G, (G, σ) has a k-colouring. Let f(n,k) be the maximum signed chromatic number of an n-vertex k-chromatic graph. This paper determines the value of f(n,k) for all positive integers n ≥ k. Then we study list colouring of signed graphs. A list assignment L of G is called symmetric if L(v) is a symmetric integer set for each vertex v. The weak signed choice number ch±w(G) of a graph G is defined to be the minimum integer k such that for any symmetric k-list assignment L of G, for any signature σ on G, there is a proper L-colouring of (G, σ). We prove that the difference ch±w(G)-χ±(G) can be arbitrarily large. On the other hand, ch±w(G) is bounded from above by twice the list vertex arboricity of G. Using this result, we prove that ch±w(K2⋆n)= χ±(K2⋆n) = ⌈2n/3⌉ + ⌊2n/3⌋. This is joint work with Ringi Kim and Xuding Zhu.

### 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.
• 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.