Source author record

Eun-Kyung Cho

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

5works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Proper conflict-free coloring of sparse graphs

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 was formally introduced by Fabrici et al., who proved that planar graphs have a proper conflict-free 8-coloring and constructed a planar graph with no proper conflict-free 5-coloring. Caro, Petruševski, and Škrekovski investigated this coloring concept further, and in particular studied upper bounds on the maximum average degree that guarantees a proper conflict-free $c$ -coloring for $c\in\{4,5,6\}$ . Along these lines, we completely determine the threshold on the maximum average degree of a graph $G$ , denoted $mad(G)$ , that guarantees a proper conflict-free $c$ -coloring for all $c$ and also provide tightness examples. Namely, for $c\geq 5$ we prove that a graph $G$ with $mad(G)\leq \frac{4c}{c+2}$ has a proper conflict-free $c$ -coloring, unless $G$ contains a $1$ -subdivision of the complete graph on $c+1$ vertices. When $c=4$ , we show that a graph $G$ with $mad(G)<\frac{12}{5}$ has a proper conflict-free $4$ -coloring, unless $G$ contains an induced $5$ -cycle. In addition, we show that a planar graph with girth at least 5 has a proper conflict-free $7$ -coloring.

preprint2020arXiv

Decomposing planar graphs into graphs with degree restrictions

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 with maximum degree at most $h$ . For $d \le 4$ , we are interested in the minimum integer $h_d$ such that every planar graph is $(d,h_d)$ -decomposable. It was known that $h_3 \le 4$ , $h_2\le 8$ , and $h_1 = \infty$ . This paper proves that $h_4=1, h_3=2$ , and $4 \le h_2 \le 6$ .

preprint2020arXiv

Generalized list colouring of graphs

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.

preprint2020arXiv

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

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 was recently disproved by Cohen-Addad et al. (2017). However, coloring planar graphs with restrictions on cycle lengths is still an active area of research, and the interest in this particular graph class remains. Let $G$ be a planar graph without $4$ -cycles and $5$ -cycles. For integers $d_1$ and $d_2$ satisfying $d_1+d_2\geq8$ and $d_2\geq d_1\geq 2$ , it is known that $V(G)$ can be partitioned into two sets $V_1$ and $V_2$ , where each $V_i$ induces a graph with maximum degree at most $d_i$ . Since Steinberg's Conjecture is false, a partition of $V(G)$ into two sets, where one induces an empty graph and the other induces a forest is not guaranteed. Our main theorem is at the intersection of the two aforementioned research directions. We prove that $V(G)$ can be partitioned into two sets $V_1$ and $V_2$ , where $V_1$ induces a forest with maximum degree at most $3$ and $V_2$ induces a forest with maximum degree at most $4$ ; this is both a relaxation of Steinberg's conjecture and a strengthening of results by Sittitrai and Nakprasit (2019) in a much stronger form.

preprint2020arXiv

The strong clique number of graphs with forbidden cycles

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 line graph of $G$ . As a relaxation of the renowned Erdős--Nešetřil conjecture regarding the strong chromatic index, Faudree et al. suggested investigating the strong clique number, and conjectured a quadratic upper bound in terms of the maximum degree. Recently, Cames van Batenburg, Kang, and Pirot conjectured a linear upper bound in terms of the maximum degree for graphs without even cycles. Namely, if $G$ is a $C_{2k}$ -free graph, then $ω_S(G)\leq (2k-1)Δ(G)-{2k-1\choose 2}$ , and if $G$ is a $C_{2k}$ -free bipartite graph, then $ω_S(G)\leq kΔ(G)-(k-1)$ . We prove the second conjecture in a stronger form, by showing that forbidding all odd cycles is not necessary. To be precise, we show that a $\{C_5, C_{2k}\}$ -free graph $G$ with $Δ(G)\ge 1$ satisfies $ω_S(G)\leq kΔ(G)-(k-1)$ , when either $k\geq 4$ or $k\in \{2,3\}$ and $G$ is also $C_3$ -free. Regarding the first conjecture, we prove an upper bound that is off by the constant term. Namely, for $k\geq 3$ , we prove that a $C_{2k}$ -free graph $G$ with $Δ(G)\ge 1$ satisfies $ω_S(G)\leq (2k-1)Δ(G)+(2k-1)^2$ . This improves some results of Cames van Batenburg, Kang, and Pirot.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Eun-Kyung Cho

Research overview

Is this your work?

5 publications

Proper conflict-free coloring of sparse graphs

Decomposing planar graphs into graphs with degree restrictions

Generalized list colouring of graphs

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

The strong clique number of graphs with forbidden cycles

See the researcher in context

Building this map preview

Eun-Kyung Cho

Research overview

Is this your work?

5 publications

Proper conflict-free coloring of sparse graphs

Decomposing planar graphs into graphs with degree restrictions

Generalized list colouring of graphs

Partitioning planar graphs without 444-cycles and 555-cycles into bounded degree forests

The strong clique number of graphs with forbidden cycles

See the researcher in context

Building this map preview

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