Eun-Kyung Cho

activity

20182025

most citedTight bound for independent domination of cubic graphs without

4

-cycles

10 citations · 21 across the 16 of their papers we have counts for

collaborators

17 papers

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

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.CO2023

Domination of subcubic planar graphs with large girth

Eun-Kyung Cho, Eric Culver, Stephen G. Hartke +1

Since Reed conjectured in 1996 that the domination number of a connected cubic graph of order $n$ is at most $⌈ \frac{1}{3} n ⌉$ , the domination number of cubic graphs has be…

math.CO2023

Independent domination versus packing in subcubic graphs

Eun-Kyung Cho, Minki Kim

In 2011, Henning, Löwenstein, and Rautenbach observed that the domination number of a graph is bounded from above by the product of the packing number and the maximum degree of the…

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★ 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.CO2022★ 3 cited

Independent domination of graphs with bounded maximum degree

Eun-Kyung Cho, Jinha Kim, Minki Kim +1

An independent dominating set of a graph, also known as a maximal independent set, is a set $S$ of pairwise non-adjacent vertices such that every vertex not in $S$ is adjacent to s…

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.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 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.CO2019

On induced saturation for paths

Eun-Kyung Cho, Ilkyoo Choi, Boram Park

For a graph $H$ , a graph $G$ is $H$ -induced-saturated if $G$ does not contain an induced copy of $H$ , but either removing an edge from $G$ or adding a non-edge to $G$ creates an in…

math.CO2018

Sharp conditions for the existence of an even $[a, b]$ -factor in a graph

Eun-Kyung Cho, Jong Yoon Hyun, Suil O +1

Let $a$ and $b$ be positive integers. An even $[a, b]$ -factor of a graph $G$ is a spanning subgraph $H$ such that for every vertex $v \in V (G)$ , $d_{H} (v)$ is even and $a \le d_H(v) \…

On Alon-Tarsi orientations of sparse graphs

Obstructions for homomorphisms to odd cycles in series-parallel graphs

Domination of subcubic planar graphs with large girth

Independent domination versus packing in subcubic graphs

Brooks-type theorems for relaxations of square colorings

Proper conflict-free coloring of sparse graphs

Odd coloring of sparse graphs and planar graphs

Independent domination of graphs with bounded maximum degree

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

On independent domination of regular graphs

Improvements on Hippchen's Conjecture

Decomposing planar graphs into graphs with degree restrictions

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

On induced saturation for paths

Sharp conditions for the existence of an even [a,b]-factor in a graph

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

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

Sharp conditions for the existence of an even $[a, b]$ -factor in a graph