This workshop brings together researchers in graph theory to share recent results and discuss new research problems related to graph theory. The workshop aims to promote research exchange and possible future collaborations among participants.
Information
Date: August 21 (Fri), 2026
Venue: Building 10-1, Room 103 @ Seoul National University.
Registration
Attendance is open to all, and no prior registration is required.
Those wishing to join the dinner are kindly asked to contact the organizer, Boram Park (borampark@snu.ac.kr) by August 10th.
Speakers
Hojin Chu (Korea Institute for Advanced Study)
Ligang Jin (Zhejiang Normal University)
Masaki Kashima (Keio University)
Hyemin Kwon (Korea Institute for Advanced Study)
Xujun Liu (Xi'an Jiaotong-Liverpool University)
Shun-ichi Maezawa (Nihon University)
Schedule
August 21 (Friday)
10:00 - 11:30 Registration and Pre-discussion
11:30 - 13:30 Lunch
Session 1 (Chair: Seog-Jin Kim)
13:30 Talk 1 (40min) Shun-ichi Maezawa
14:10 Talk 2 (40min) Ligang Jin
(10 minutes break)
15:00 Talk 3 (40min) Hyemin Kwon
15:40 Coffee Break/Group Photo
Session 2 (Chair: Ringi Kim)
16:10 Talk 4 (40min) Masaki Kashima
16:50 Talk 5 (40min) Hojin Chu
(10 minutes break)
17:40 Talk 6 (40min) Xujun Liu
18:40 - 20:30 Banquet
Abstract
Talk 1 Shun-ichi Maezawa
Title: Forbidden monochromatic subgraph conditions for complete edge-colored graphs to have properly colored Hamilton paths
Abstract: A path in an edge-colored graph is called properly colored (PC) if no two consecutive edges receive the same color. In this talk, we show that every edge-colored complete graph containing no monochromatic subgraph from a certain small family contains a PC Hamilton path, apart from an easily described exceptional class. We also discuss related problems and possible extensions.
Talk 2 Ligang Jin
Title: DP coloring of graphs and edge coloring of signed graphs
Abstract: The concept of DP-coloring of graphs was introduced by Dvo\v{r}\'{a}k and Postle in 2018, and was used to prove that planar graphs without cycles of length from $4$ to $8$ are $3$-choosable. In the same paper, they proposed a more natural and stronger claim that such graphs are DP-$3$-colorable. Recently, we confirm this claim by proving a stronger result that planar graphs having no cycle of length $4$, $6$ or $8$ are DP-3-colorable. This is joint work with Yingli Kang and Xuding Zhu. In this talk, I will present the proof of this result. The proof uses the concept of coloring of generalized signed graphs.
Besides, I will present a new result on edge coloring of signed graphs. It was known that an analogy of Vizing's Adjacency Lemma holds for signed graphs with even maximum. We generalize some more adjacency lemmas to signed graphs with even maximum. As an application, we use them to prove partial results to the signed version of Vizing' Planar Graph Conjecture with $\Delta=6$. This is joint work with Jing Huang and Yingli Kang.
Talk 3 Hyemin Kwon
Title:
Abstract:
Talk 4 Masaki Kashima
Title: On Gr\"{u}nbaum's conjecture on longest cycles and paths
Abstract: In 1974, Gr\"{u}nbaum introduced a class $\Gamma(k,k)$ of graphs that consists of graphs with circumference exactly their order minus $k$, and the deletion of every set of $k$ vertices from the graph yields a Hamiltonian graph. In particular, when $k=1$, the class $\Gamma(1,1)$ is the set of graphs that are not Hamiltonian, but the deletion of any single vertex leads to a Hamiltonian graph, which are called hypohamiltonian graphs. While it is known that there are infinitely many hypohamiltonian graphs, Gr\"{u}nbaum conjectured that $\Gamma(k,k)$ is empty for all integers $k$ at least 2, which is still widely open. We consider the graphs in $\Gamma(k,k)$ with the specified order, and give an upper bound on the maximum degree of $n$-vertex graphs in $\Gamma(k,k)$ in terms of $n$ and $k$. As a consequence, we obtain a lower bound on the order of graphs in $\Gamma(k,k)$. We also investigate the analogous problem for longest paths. This is a joint work with Kenta Ozeki and Leilei Zhang.
Talk 5 Hojin Chu
Title: Cycles modulo 3 and 4: Extremal and Structural results
Abstract: Burr and Erd\H{o}s conjectured that, whenever the residue class $\ell \pmod{k}$ contains an even integer, every graph containing no cycle of length $\ell$ modulo $k$ has at most linearly many edges. Bollob\'{a}s proved this conjecture, and Erd\H{o}s subsequently asked for the corresponding exact extremal numbers. A related conjecture of Dean asserts that every graph of minimum degree at least $k$ contains a cycle whose length is divisible by $k$. In this talk, we present extremal and structural results for cycles modulo $3$ and $4$. We establish sharp edge bounds for $2$-connected graphs containing no cycle of length $1$ modulo $3$, $2$ modulo $4$, or $0$ modulo $4$, and describe the extremal graphs in several cases. We also characterize graphs with minimum degree at least $2$ and few vertices of degree $2$ that contain no cycle of length divisible by $3$ or $4$, strengthening results related to the corresponding cases of Dean's conjecture.
Talk 6 Xujun Liu
Title: Packing colorings of subcubic graphs
Abstract: For a sequence $S = (s_1, \ldots, s_k)$ of non-decreasing positive integers, a packing $S$-coloring of a graph $G$ is a partition of its vertex set $V(G)$ into $V_1, \ldots, V_k$ such that for every pair of distinct vertices $u,v \in V_i$ the distance between $u$ and $v$ is at least $s_i+1$, where $1 \le i \le k$. The packing chromatic number, $\chi_p(G)$, of a graph $G$ is defined to be the smallest integer $k$ such that $G$ has a packing~$(1,2, \ldots, k)$-coloring. Gastineau and Togni asked an open question ``Is it true that the $1$-subdivision ($D(G)$) of any subcubic graph $G$ has packing chromatic number at most $5$?'' and later Bre\v sar, Klav\v zar, Rall, and Wash conjectured that it is true. In a recent joint work with X. Hou and X. Wang, we proved the conjecture. Furthermore, Gastineau and Togni also asked ``Is it true that every subcubic graph except the Petersen graph is packing $(1,2,2,2,2,2)$-colorable?''. In a recent joint work with Y. Wang, we proved the open problem for subcubic planar graphs. We will talk about both results in this talk.
Organizer
Boram Park (Seoul National University)
Staff
Gyuseong Jang (Seoul National University)
Support
National Research Foundation of Korea
Seoul National University