Tag: 김석진

The square of a graph $G$, denoted $G^2$, has the same vertex set as $G$ and has an edge between two vertices if the distance between them in $G$ is at most $2$. Wegner’s conjecture (1977) states that for a planar graph $G$, the chromatic number $\chi (G^2)$ of $G^2$ is at most 7 if $\mathrm{\Delta }(G)=3$, at most $\mathrm{\Delta }(G)+5$ if $4\le \mathrm{\Delta }(G)\le 7$, and at most $\lfloor \frac{3\mathrm{\Delta }(G)}{2}\rfloor$ if $\mathrm{\Delta }(G)\ge 8$. Wegner’s conjecture is still wide open. The only case for which we know tight bound is when $\mathrm{\Delta }(G)=3$. Thomassen (2018) showed that $\chi (G^2)\le 7$ if $G$ is a planar graph with $\mathrm{\Delta }(G)=3$, which implies that Wegner’s conjecture is true for $\mathrm{\Delta }(G)=3$. A natural question is whether ${\chi }_{\ell }(G^2)\le 7$ or not if $G$ is a subcubic planar graph, where ${\chi }_{\ell }(G^2)$ is the list chromatic number of $G^2$. Cranston and Kim (2008) showed that ${\chi }_{\ell }(G^2)\le 7$ if $G$ is a subcubic planar graph of girth at least 7. We prove that ${\chi }_{\ell }(G^2)\le 7$ if $G$ is a subcubic planar graph of girth at least 6. This is joint work with Xiaopan Lian (Nankai University).

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.

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.