On July 7, 2020, Seog-jin Kim (김석진) from Konkuk University presented his work on the online DP-coloring of graphs, a common generalization of the online coloring and the DP coloring, both generalizing the list coloring of graphs. The title of his talk was “Online DP-coloring of graphs“. He will stay at the IBS discrete mathematics group until the end of this week.

## Seog-Jin Kim (김석진), Online DP-coloring of graphs

Online list coloring and DP-coloring are generalizations of list coloring that attracted considerable attention recently. Each of the paint number, $\chi_P(G)$, (the minimum number of colors needed for an online coloring of $G$) and the DP-chromatic number, $\chi_{DP}(G)$, (the minimum number of colors needed for a DP-coloring of $G$) is at least the list chromatic number, $\chi_\ell(G)$, of $G$ and can be much larger. On the other hand, each of them has a number of useful properties.

We introduce a common generalization, online DP-coloring, of online list coloring and DP-coloring and to study its properties. This is joint work with Alexandr Kostochka, Xuer Li, and Xuding Zhu.

## Seog-Jin Kim presented his work on signed colouring and list colouring of k-chromatic graphs on January 28

Seog-Jin Kim from Konkuk University presented a talk at Discrete Math Seminar on January 28, 2019. The title of his talk was “Signed colouring and list colouring of k-chromatic graphs.”

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

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) → N_{k} such that for each edge e=uv, f(x)≠σ(e) f(y), where N_{k} 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}(K_{2⋆n})= χ_{±}(K_{2⋆n}) = ⌈2n/3⌉ + ⌊2n/3⌋. This is joint work with Ringi Kim and Xuding Zhu.