Ilkyoo Choi

activity

20132026

most citedStrong edge-colorings of sparse graphs with large maximum degree

17 citations · 116 across the 43 of their papers we have counts for

collaborators

Showing math.COShow all

46 papers · 1 filter

math.CO2026

Induced-saturated graphs exist for even cycles

Ilkyoo Choi

A graph $G$ is \emph{ $H$ -induced-saturated} if $G$ has no induced subgraph isomorphic to $H$ but changing the adjacency of an arbitrary pair of vertices in $G$ creates an induced c…

math.CO2026

Existence of cycles of length divisible by 3 or 4

Ilkyoo Choi, Hojin Chu, Ringi Kim +1

Dean conjectured that for each integer $k \geq 3$ , every graph with minimum degree at least $k$ has a cycle whose length is divisible by $k$ ; this conjecture is known to be true for…

math.CO2025

Flexible DP 3-coloring of sparse multigraphs

Peter Bradshaw, Ilkyoo Choi, Alexandr Kostochka

A \emph{request} on a graph assigns a preferred color to a subset of the vertices. A graph $G$ is \emph{ $ε$ -flexibly $k$ -choosable} if for every $k$ -list assignment $L$ and every r…

math.CO2025

Between proper and square colorings of sparse graphs

Ilkyoo Choi, Xujun Liu

An $i$ -independent set is a set of vertices whose pairwise distance is at least $i + 1$ . A proper coloring (resp. a square coloring) of a graph is a partition of its vertices into in…

math.CO2025

On Alon-Tarsi orientations of sparse graphs

Eun-Kyung Cho, Ilkyoo Choi, Boram Park +1

Assume $G$ is a graph, $(v_{1}, \dots, v_{k})$ is a sequence of distinct vertices of $G$ , and $(a_{1}, \dots, a_{k})$ is an integer sequence with $a_{i} \in {1, 2}$ . We say $G$ is \emph{$(a_1…

math.CO2025

Partition of Sparse Multigraphs into a Forest and a Forest with Restrictions

Ilkyoo Choi, Alexandr V. Kostochka, Matthew Yancey

The following measure of sparsity of multigraphs refining the maximum average degree: For $a > 0$ and an arbitrary real $b$ , a multigraph $H$ is \emph{ $(a, b)$ -sparse} if it is loople…

math.CO2025

Obstructions for homomorphisms to odd cycles in series-parallel graphs

Eun-Kyung Cho, Ilkyoo Choi, Boram Park +1

For a graph $H$ , an $H$ -colouring of a graph $G$ is a vertex map $ϕ : V (G) \to V (H)$ such that adjacent vertices are mapped to adjacent vertices. A graph $G$ is $C_{2 k + 1}$ -critical i…

math.CO2024

A lower bound on the number of edges in DP-critical graphs. II. Four colors

Peter Bradshaw, Ilkyoo Choi, Alexandr Kostochka +1

A graph $G$ is $k$ -critical (list $k$ -critical, DP $k$ -critical) if $χ (G) = k$ ( $χ_{ℓ} (G) = k$ , $χ_{DP} (G) = k$ ) and for every proper subgraph $G^{'}$ of $G$ , $χ (G^{'}) < k$ ($χ_\ell(…

math.CO2024

A lower bound on the number of edges in DP-critical graphs

Peter Bradshaw, Ilkyoo Choi, Alexandr Kostochka +1

math.CO2023

Brooks-type theorems for relaxations of square colorings

Eun-Kyung Cho, Ilkyoo Choi, Hyemin Kwon +1

The following relaxation of proper coloring the square of a graph was recently introduced: for a positive integer $h$ , the proper $h$ -conflict-free chromatic number of a graph $G$ ,…

math.CO2022

Relaxation of Wegner's Planar Graph Conjecture for maximum degree 4

Eun-Kyung Cho, Ilkyoo Choi, Bernard Lidický

The famous Wegner's Planar Graph Conjecture asserts tight upper bounds on the chromatic number of the square $G^{2}$ of a planar graph $G$ , depending on the maximum degree $Δ (G)$ of…

math.CO2022★ 5 cited

Proper conflict-free coloring of sparse graphs

Eun-Kyung Cho, Ilkyoo Choi, Hyemin Kwon +1

A {\it proper conflict-free $c$ -coloring} of a graph is a proper $c$ -coloring such that each non-isolated vertex has a color appearing exactly once on its neighborhood. This notion…

math.CO2022★ 1 cited

Odd coloring of sparse graphs and planar graphs

Eun-Kyung Cho, Ilkyoo Choi, Hyemin Kwon +1

An {\it odd $c$ -coloring} of a graph is a proper $c$ -coloring such that each non-isolated vertex has a color appearing an odd number of times on its neighborhood. This concept was…

math.CO2021★ 10 cited

Tight bound for independent domination of cubic graphs without $4$ -cycles

Eun-Kyung Cho, Ilkyoo Choi, Hyemin Kwon +1

Given a graph $G$ , a dominating set of $G$ is a set $S$ of vertices such that each vertex not in $S$ has a neighbor in $S$ . The domination number of $G$ , denoted $γ (G)$ , is the min…

math.CO2021

On independent domination of regular graphs

Eun-Kyung Cho, Ilkyoo Choi, Boram Park

Given a graph $G$ , a dominating set of $G$ is a set $S$ of vertices such that each vertex not in $S$ has a neighbor in $S$ . The domination number of $G$ , denoted $γ (G)$ , is the min…

math.CO2021

Brick partition problems in three dimensions

Ilkyoo Choi, Minseong Kim, Kiwon Seo

A $d$ -dimensional brick is a set $I_{1} \times \dots \times I_{d}$ where each $I_{i}$ is an interval. Given a brick $B$ , a brick partition of $B$ is a partition of $B$ into bricks. A bri…

math.CO2020

Improvements on Hippchen's Conjecture

Eun-Kyung Cho, Ilkyoo Choi, Boram Park

Let $G$ be a $k$ -connected graph on $n$ vertices. Hippchen's Conjecture states that two longest paths in $G$ share at least $k$ vertices. Gutiérrez recently proved the conjecture w…

math.CO2020

Decomposing planar graphs into graphs with degree restrictions

Eun-Kyung Cho, Ilkyoo Choi, Ringi Kim +3

Given a graph $G$ , a decomposition of $G$ is a partition of its edges. A graph is $(d, h)$ -decomposable if its edge set can be partitioned into a $d$ -degenerate graph and a graph w…

math.CO2020★ 1 cited

The layer number of $α$ -evenly distributed point sets

Ilkyoo Choi, Weonyoung Joo, Minki Kim

For a finite point set in $R^{d}$ , we consider a peeling process where the vertices of the convex hull are removed at each step. The layer number $L (X)$ of a given point set…

math.CO2020★ 1 cited

The strong clique number of graphs with forbidden cycles

Eun-Kyung Cho, Ilkyoo Choi, Ringi Kim +1

Given a graph $G$ , the strong clique number of $G$ , denoted $ω_{S} (G)$ , is the maximum size of a set $S$ of edges such that every pair of edges in $S$ has distance at most $2$ in the…

math.CO2020

Partitioning planar graphs without $4$ -cycles and $5$ -cycles into bounded degree forests

Eun-Kyung Cho, Ilkyoo Choi, Boram Park

In 1976, Steinberg conjectured that planar graphs without $4$ -cycles and $5$ -cycles are $3$ -colorable. This conjecture attracted numerous researchers for about 40 years, until it w…

math.CO2020★ 1 cited

Generalized list colouring of graphs

Eun-Kyung Cho, Ilkyoo Choi, Yiting Jiang +4

This paper disproves a conjecture of Wang, Wu, Yan and Xie, and answers in negative a question in Dvorak, Pekarek and Sereni. In return, we pose five open problems.

math.CO2020

A sharp Ore-type condition for a connected graph with no induced star to have a Hamiltonian path

Ilkyoo Choi, Jinha Kim

We say a graph $G$ has a Hamiltonian path if it has a path containing all vertices of $G$ . For a graph $G$ , let $σ_{2} (G)$ denote the minimum degree sum of two nonadjacent vertices o…

math.CO2019★ 2 cited

Planar graphs with girth at least 5 are (3,4)-colorable

Ilkyoo Choi, Gexin Yu, Xia Zhang

A graph is $(d_{1}, \dots, d_{k})$ -colorable if its vertex set can be partitioned into $k$ nonempty subsets so that the subgraph induced by the $i$ th part has maximum degree at most $…

Induced-saturated graphs exist for even cycles

Existence of cycles of length divisible by 3 or 4

Flexible DP 3-coloring of sparse multigraphs

Between proper and square colorings of sparse graphs

On Alon-Tarsi orientations of sparse graphs

Partition of Sparse Multigraphs into a Forest and a Forest with Restrictions

Obstructions for homomorphisms to odd cycles in series-parallel graphs

A lower bound on the number of edges in DP-critical graphs. II. Four colors

A lower bound on the number of edges in DP-critical graphs

Brooks-type theorems for relaxations of square colorings

Relaxation of Wegner's Planar Graph Conjecture for maximum degree 4

Proper conflict-free coloring of sparse graphs

Odd coloring of sparse graphs and planar graphs

Tight bound for independent domination of cubic graphs without 4-cycles

On independent domination of regular graphs

Brick partition problems in three dimensions

Improvements on Hippchen's Conjecture

Decomposing planar graphs into graphs with degree restrictions

The layer number of α-evenly distributed point sets

The strong clique number of graphs with forbidden cycles

Partitioning planar graphs without 4-cycles and 5-cycles into bounded degree forests

Generalized list colouring of graphs

A sharp Ore-type condition for a connected graph with no induced star to have a Hamiltonian path

Planar graphs with girth at least 5 are (3,4)-colorable

Tight bound for independent domination of cubic graphs without $4$ -cycles

The layer number of $α$ -evenly distributed point sets

Partitioning planar graphs without $4$ -cycles and $5$ -cycles into bounded degree forests