Seog-Jin Kim

activity

20092026

most citedThe competition number of a graph with exactly two holes

8 citations · 50 across the 23 of their papers we have counts for

collaborators

25 papers

math.CO2026

On $(1, 2^{4})$ and $(1, 2^{5})$ -packing edge-coloring of sparse subcubic graphs

Seog-Jin Kim, Xujun Liu, Boyan Xu

A $(1^{j}, 2^{k})$ -packing edge-coloring of a graph $G$ is a partition of the edge set $E (G)$ into $j$ matchings and $k$ induced matchings. Hocquard, Lajou, and Lu\v zar found a subcubi…

math.CO2023

The square of every subcubic planar graph of girth at least 6 is 7-choosable

Seog-Jin Kim, Xiaopan Lian

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$ . Thomassen (2018) a…

math.CO2020★ 2 cited

$K_{r + 1}$ -saturated graphs with small spectral radius

Jaehoon Kim, Seog-Jin Kim, Alexandr V. Kostochka +1

For a graph $H$ , a graph $G$ is $H$ -saturated if $G$ does not contain $H$ as a subgraph but for any $e \in E (G)$ , $G + e$ contains $H$ . In this note, we prove a sharp lowe…

math.CO2019

The Alon-Tarsi number of $K_{5}$ -minor-free graphs

Toshiki Abe, Seog-Jin Kim, Kenta Ozeki

In this paper, we show the following three theorems. Let $G$ be a $K_{5}$ -minor-free graph. Then Alon-Tarsi number of $G$ is at most $5$ , there exists a matching $M$ of $G$ such that…

math.CO2019

On list 3-dynamic coloring of near-triangulations

Ruijuan Gu, Seog-Jin Kim, Yulai Ma +1

An $r$ -dynamic $k$ -coloring of a graph $G$ is a proper $k$ -coloring such that for any vertex $v$ , there are at least $min {r, d e g_{G} (v)}$ distinct colors in $N_{G} (v)$ . The $r$ -dyn…

math.CO2019

Planar graphs without 7-cycles and butterflies are DP-4-colorable

Seog-Jin Kim, Runrun Liu, Gexin Yu

DP-coloring (also known as correspondence coloring) is a generalization of list coloring, introduced by Dvořák and Postle in 2017. It is well-known that there are non-4-choosable p…

math.CO2019★ 5 cited

The Alon-Tarsi number of subgraphs of a planar graph

Ringi Kim, Seog-Jin Kim, Xuding Zhu

This paper constructs a planar graph $G_{1}$ such that for any subgraph $H$ of $G_{1}$ with maximum degree $Δ (H) \leq 3$ , $G_{1} - E (H)$ is not $3$ -choosable, and a planar graph $G_{2}$ such…

math.CO2019

Coloring squares of graphs with mad constraints

Hervé Hocquard, Seog-Jin Kim, Théo Pierron

A proper vertex $k$ -coloring of a graph $G = (V, E)$ is an assignment $c : V \to {1, 2, \dots, k}$ of colors to the vertices of the graph such that no two adjacent vertices are associate…

math.CO2017★ 6 cited

Planar graphs without 4-cycles adjacent to triangles are DP-4-colorable

Seog-Jin Kim, Xiaowei Yu

DP-coloring (also known as correspondence coloring) of a simple graph is a generalization of list coloring. It is known that planar graphs without 4-cycles adjacent to triangles ar…

math.CO2017★ 5 cited

A Sufficient condition for DP-4-colorability

Seog-Jin Kim, Kenta Ozeki

DP-coloring of a simple graph is a generalization of list coloring, and also a generalization of signed coloring of signed graphs. It is known that for each $k \in {3, 4, 5, 6}$ ,…

math.CO2017★ 3 cited

A note on a Brooks' type theorem for DP-coloring

Seog-Jin Kim, Kenta Ozeki

Dvořák and Postle \cite{DP} introduced a \textit{DP-coloring} of a simple graph as a generalization of a list-coloring. They proved a Brooks' type theorem for a DP-coloring, and Be…

math.CO2016★ 4 cited

Cycles with two blocks in $k$ -chromatic digraphs

Ringi Kim, Seog-Jin Kim, Jie Ma +1

Let $k$ and $ℓ$ be positive integers. A cycle with two blocks $c (k, ℓ)$ is an oriented cycle which consists of two internally (vertex) disjoint directed paths of lengths at le…

math.CO2016★ 1 cited

List 3-dynamic coloring of graphs with small maximum average degree

Seog-Jin Kim, Boram Park

An $r$ -dynamic $k$ -coloring of a graph $G$ is a proper $k$ -coloring such that for any vertex $v$ , there are at least $min {r, °_{G} (v)}$ distinct colors in $N_{G} (v)$ . The $r$ -dynami…

math.CO2015★ 1 cited

Coloring the squares of graphs whose maximum average degrees are less than 4

Seog-Jin Kim, Boram Park

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. The…

math.CO2015

List-coloring the Square of a Subcubic Graph

Daniel W. Cranston, Seog-Jin Kim

The {\em square} $G^{2}$ of a graph $G$ is the graph with the same vertex set as $G$ and with two vertices adjacent if their distance in $G$ is at most 2. Thomassen showed that every…

math.CO2015★ 1 cited

Decomposition of Sparse Graphs into Forests: The Nine Dragon Tree Conjecture for $k \leq 2$

Min Chen, Seog-Jin Kim, Alexandr Kostochka +2

For a loopless multigraph $G$ , the fractional arboricity $A r b (G)$ is the maximum of $\frac{∣ E ( H ) ∣}{∣ V ( H ) ∣ - 1}$ over all subgraphs $H$ with at least two vertices. Generalizing the Na…

math.CO2014

Bipartite graphs whose squares are not chromatic-choosable

Seog-Jin Kim, Boram Park

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…

math.CO2014★ 1 cited

Coloring of the square of Kneser graph $K (2 k + r, k)$

Seog-Jin Kim, Boram Park

The Kneser graph $K (n, k)$ is the graph whose vertices are the $k$ -element subsets of an $n$ elements set, with two vertices adjacent if they are disjoint. The square $G^{2}$ of a gra…

math.CO2013★ 2 cited

Chromatic-choosability of the power of graphs

Seog-Jin Kim, Young Soo Kwon, Boram Park

The $k$ th power $G^{k}$ of a graph $G$ is the graph defined on $V (G)$ such that two vertices $u$ and $v$ are adjacent in $G^{k}$ if the distance between $u$ and $v$ in $G$ is at most $…

math.CO2013★ 5 cited

Counterexamples to the List Square Coloring Conjecture

Seog-Jin Kim, Boram Park

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…

math.CO2013

Improved bounds on the chromatic numbers of the square of Kneser graphs

Seog-Jin Kim, Boram Park

The Kneser graph $K (n, k)$ is the graph whose vertices are the $k$ -elements subsets of an $n$ -element set, with two vertices adjacent if the sets are disjoint. The square $G^{2}$ of a…

math.CO2010

Injective colorings of sparse graphs

Daniel W. Cranston, Seog-Jin Kim, Gexin Yu

Let $ma d (G)$ denote the maximum average degree (over all subgraphs) of $G$ and let $χ_{i} (G)$ denote the injective chromatic number of $G$ . We prove that if $ma d (G) \leq 5/2$ , then $…

math.CO2010

Injective colorings of graphs with low average degree

Daniel W. Cranston, Seog-Jin Kim, Gexin Yu

Let $\mad(G)$ denote the maximum average degree (over all subgraphs) of $G$ and let $χ_{i} (G)$ denote the injective chromatic number of $G$ . We prove that if $Δ \geq 4$ and $\mad(G)<\…

math.CO2009★ 8 cited

The competition number of a graph with exactly two holes

Jung Yeun Lee, Suh-Ryung Kim, Seog-Jin Kim +1

Let D be an acyclic digraph. The competition graph of D is a graph which has the same vertex set as D and has an edge between x and y if and only if there exists a vertex v in D su…

On (1,24) and (1,25)-packing edge-coloring of sparse subcubic graphs

The square of every subcubic planar graph of girth at least 6 is 7-choosable

Kr+1​-saturated graphs with small spectral radius

The Alon-Tarsi number of K5​-minor-free graphs

On list 3-dynamic coloring of near-triangulations

Planar graphs without 7-cycles and butterflies are DP-4-colorable

The Alon-Tarsi number of subgraphs of a planar graph

Coloring squares of graphs with mad constraints

Planar graphs without 4-cycles adjacent to triangles are DP-4-colorable

A Sufficient condition for DP-4-colorability

A note on a Brooks' type theorem for DP-coloring

Cycles with two blocks in k-chromatic digraphs

List 3-dynamic coloring of graphs with small maximum average degree

Coloring the squares of graphs whose maximum average degrees are less than 4

List-coloring the Square of a Subcubic Graph

Decomposition of Sparse Graphs into Forests: The Nine Dragon Tree Conjecture for k≤2

Bipartite graphs whose squares are not chromatic-choosable

Coloring of the square of Kneser graph K(2k+r,k)

Chromatic-choosability of the power of graphs

Counterexamples to the List Square Coloring Conjecture

Improved bounds on the chromatic numbers of the square of Kneser graphs

Injective colorings of sparse graphs

Injective colorings of graphs with low average degree

The competition number of a graph with exactly two holes

On $(1, 2^{4})$ and $(1, 2^{5})$ -packing edge-coloring of sparse subcubic graphs

$K_{r + 1}$ -saturated graphs with small spectral radius

The Alon-Tarsi number of $K_{5}$ -minor-free graphs

Cycles with two blocks in $k$ -chromatic digraphs

Decomposition of Sparse Graphs into Forests: The Nine Dragon Tree Conjecture for $k \leq 2$

Coloring of the square of Kneser graph $K (2 k + r, k)$