Source author record

Ilkyoo Choi

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

15works

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.

preprint2021arXiv

Brick partition problems in three dimensions

A $d$ -dimensional brick is a set $I_1\times \cdots \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 brick partition $\mathcal{P}_d$ of a $d$ -dimensional brick is $k$ -piercing if every axis-parallel line intersects at least $k$ bricks in $\mathcal{P}_d$ . Bucic et al. explicitly asked the minimum size $p(d, k)$ of a $k$ -piercing brick partition of a $d$ -dimensional brick. The answer is known to be $4(k-1)$ when $d=2$ . Our first result almost determines $p(3, k)$ . Namely, we construct a $k$ -piercing brick partition of a $3$ -dimensional brick with $12k-15$ parts, which is off by only $1$ from the known lower bound. As a generalization of the above question, we also seek the minimum size $s(d, k)$ of a brick partition $\mathcal{P}_d$ of a $d$ -dimensional brick where each axis-parallel plane intersects at least $k$ bricks in $\mathcal{P}_d$ . We resolve the question in the $3$ -dimensional case by determining $s(3, k)$ for all $k$ .

preprint2020arXiv

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

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 of $G$ ; restrictions on $σ_2(G)$ are known as Ore-type conditions. Given an integer $t\geq 5$ , we prove that if a connected graph $G$ on $n$ vertices satisfies $σ_2(G)>{t-3\over t-2}n$ , then $G$ has either a Hamiltonian path or an induced subgraph isomorphic to $K_{1, t}$ . Moreover, we characterize all $n$ -vertex graphs $G$ where $σ_2(G)={t-3\over t-2}n$ and $G$ has neither a Hamiltonian path nor an induced subgraph isomorphic to $K_{1, t}$ . This is an analogue of a recent result by Momège, who investigated the case when $t=4$ .

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

Inducibility of directed paths

A long standing open problem in extremal graph theory is to describe all graphs that maximize the number of induced copies of a path on four vertices. The character of the problem changes in the setting of oriented graphs, and becomes more tractable. Here we resolve this problem in the setting of oriented graphs without transitive triangles.

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 layer number of $α$ -evenly distributed point sets

For a finite point set in $\mathbb{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 $X$ is defined as the number of steps of the peeling process in order to delete all points in $X$ . It is known that if $X$ is a set of random points in $\mathbb{R}^d$ , then the expectation of $L(X)$ is $Θ(|X|^{2/(d+1)})$ , and recently it was shown that if $X$ is a point set of the square grid on the plane, then $L(X)=Θ(|X|^{2/3})$ . In this paper, we investigate the layer number of $α$ -evenly distributed point sets for $α>1$ ; these point sets share the regularity aspect of random point sets but in a more general setting. The set of lattice points is also an $α$ -evenly distributed point set for some $α>1$ . We find an upper bound of $O(|X|^{3/4})$ for the layer number of an $α$ -evenly distributed point set $X$ in a unit disk on the plane for some $α>1$ , and provide an explicit construction that shows the growth rate of this upper bound cannot be improved. In addition, we give an upper bound of $O(|X|^{\frac{d+1}{2d}})$ for the layer number of an $α$ -evenly distributed point set $X$ in a unit ball in $\mathbb{R}^d$ for some $α>1$ and $d\geq 3$ .

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.

preprint2019arXiv

Online Ramsey theory for a triangle on $F$ -free graphs

Given a class $\mathcal{C}$ of graphs and a fixed graph $H$ , the online Ramsey game for $H$ on $\mathcal C$ is a game between two players Builder and Painter as follows: an unbounded set of vertices is given as an initial state, and on each turn Builder introduces a new edge with the constraint that the resulting graph must be in $\mathcal C$ , and Painter colors the new edge either red or blue. Builder wins the game if Painter is forced to make a monochromatic copy of $H$ at some point in the game. Otherwise, Painter can avoid creating a monochromatic copy of $H$ forever, and we say Painter wins the game. We initiate the study of characterizing the graphs $F$ such that for a given graph $H$ , Painter wins the online Ramsey game for $H$ on $F$ -free graphs. We characterize all graphs $F$ such that Painter wins the online Ramsey game for $C_3$ on the class of $F$ -free graphs, except when $F$ is one particular graph. We also show that Painter wins the online Ramsey game for $C_3$ on the class of $K_4$ -minor-free graphs, extending a result by Grytczuk, Hałuszczak, and Kierstead.

preprint2016arXiv

On tiling the integers with $4$ -sets of the same gap sequence

Partitioning a set into similar, if not, identical, parts is a fundamental research topic in combinatorics. The question of partitioning the integers in various ways has been considered throughout history. Given a set $\{x_1, \ldots, x_n\}$ of integers where $x_1<\cdots<x_n$ , let the {\it gap sequence} of this set be the nondecreasing sequence $d_1, \ldots, d_{n-1}$ where $\{d_1, \ldots, d_{n-1}\}$ equals $\{x_{i+1}-x_i:i\in\{1,\ldots, n-1\}\}$ as a multiset. This paper addresses the following question, which was explicitly asked by Nakamigawa: can the set of integers be partitioned into sets with the same gap sequence? The question is known to be true for any set where the gap sequence has length at most two. This paper provides evidence that the question is true when the gap sequence has length three. Namely, we prove that given positive integers $p$ and $q$ , there is a positive integer $r_0$ such that for all $r\geq r_0$ , the set of integers can be partitioned into $4$ -sets with gap sequence $p, q$ , $r$ .

preprint2014arXiv

$(1, k)$ -coloring of graphs with girth at least $5$ on a surface

A graph is $(d_1, ..., d_r)$ -colorable if its vertex set can be partitioned into $r$ sets $V_1, ..., V_r$ so that the maximum degree of the graph induced by $V_i$ is at most $d_i$ for each $i\in \{1, ..., r\}$ . For a given pair $(g, d_1)$ , the question of determining the minimum $d_2=d_2(g; d_1)$ such that planar graphs with girth at least $g$ are $(d_1, d_2)$ -colorable has attracted much interest. The finiteness of $d_2(g; d_1)$ was known for all cases except when $(g, d_1)=(5, 1)$ . Montassier and Ochem explicitly asked if $d_2(5; 1)$ is finite. We answer this question in the affirmative with $d_2(5; 1)\leq 10$ ; namely, we prove that all planar graphs with girth at least $5$ are $(1, 10)$ -colorable. Moreover, our proof extends to the statement that for any surface $S$ of Euler genus $γ$ , there exists a $K=K(γ)$ where graphs with girth at least $5$ that are embeddable on $S$ are $(1, K)$ -colorable. On the other hand, there is no finite $k$ where planar graphs (and thus embeddable on any surface) with girth at least $5$ are $(0, k)$ -colorable.

preprint2013arXiv

On Choosability with Separation of Planar Graphs with Forbidden Cycles

We study choosability with separation which is a constrained version of list coloring of graphs. A (k,d)-list assignment L on a graph G is a function that assigns to each vertex v a list L(v) of at least k colors and for any adjacent pair xy, the lists L(x) and L(y) share at most d colors. A graph G is (k,d)-choosable if there exists an L-coloring of G for every (k,d)-list assignment L. This concept is also known as choosability with separation. We prove that planar graphs without 4-cycles are (3,1)-choosable and that planar graphs without 5-cycles and 6-cycles are (3,1)-choosable. In addition, we give an alternative and slightly stronger proof that triangle-free planar graphs are $(3,1)$ -choosable.

preprint2013arXiv

Toroidal graphs containing neither $K_5^{-}$ nor 6-cycles are 4-choosable

The choosability $χ_\ell(G)$ of a graph $G$ is the minimum $k$ such that having $k$ colors available at each vertex guarantees a proper coloring. Given a toroidal graph $G$ , it is known that $χ_\ell(G)\leq 7$ , and $χ_\ell(G)=7$ if and only if $G$ contains $K_7$ . Cai, Wang, and Zhu proved that a toroidal graph $G$ without 7-cycles is 6-choosable, and $χ_\ell(G)=6$ if and only if $G$ contains $K_6$ . They also prove that a toroidal graph $G$ without 6-cycles is 5-choosable, and conjecture that $χ_\ell(G)=5$ if and only if $G$ contains $K_5$ . We disprove this conjecture by constructing an infinite family of non-4-colorable toroidal graphs with neither $K_5$ nor cycles of length at least 6; moreover, this family of graphs is embeddable on every surface except the plane and the projective plane. Instead, we prove the following slightly weaker statement suggested by Zhu: toroidal graphs containing neither $K^-_5$ (a $K_5$ missing one edge) nor 6-cycles are 4-choosable. This is sharp in the sense that forbidding only one of the two structures does not ensure that the graph is 4-choosable.

preprint2013arXiv

Vertex Arboricity of Toroidal Graphs with a Forbidden Cycle

The vertex arboricity $a(G)$ of a graph $G$ is the minimum $k$ such that $V(G)$ can be partitioned into $k$ sets where each set induces a forest. For a planar graph $G$ , it is known that $a(G)\leq 3$ . In two recent papers, it was proved that planar graphs without $k$ -cycles for some $k\in\{3, 4, 5, 6, 7\}$ have vertex arboricity at most 2. For a toroidal graph $G$ , it is known that $a(G)\leq 4$ . Let us consider the following question: do toroidal graphs without $k$ -cycles have vertex arboricity at most 2? It was known that the question is true for k=3, and recently, Zhang proved the question is true for $k=5$ . Since a complete graph on 5 vertices is a toroidal graph without any $k$ -cycles for $k\geq 6$ and has vertex arboricity at least three, the only unknown case was k=4. We solve this case in the affirmative; namely, we show that toroidal graphs without 4-cycles have vertex arboricity at most 2.

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.

Ilkyoo Choi

Research overview

Is this your work?

15 publications

Proper conflict-free coloring of sparse graphs

Brick partition problems in three dimensions

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

Decomposing planar graphs into graphs with degree restrictions

Generalized list colouring of graphs

Inducibility of directed paths

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

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

The strong clique number of graphs with forbidden cycles

Online Ramsey theory for a triangle on $F$ -free graphs

On tiling the integers with $4$ -sets of the same gap sequence

$(1, k)$ -coloring of graphs with girth at least $5$ on a surface

On Choosability with Separation of Planar Graphs with Forbidden Cycles

Toroidal graphs containing neither $K_5^{-}$ nor 6-cycles are 4-choosable

Vertex Arboricity of Toroidal Graphs with a Forbidden Cycle

See the researcher in context

Building this map preview

Ilkyoo Choi

Research overview

Is this your work?

15 publications

Proper conflict-free coloring of sparse graphs

Brick partition problems in three dimensions

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

Decomposing planar graphs into graphs with degree restrictions

Generalized list colouring of graphs

Inducibility of directed paths

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

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

The strong clique number of graphs with forbidden cycles

Online Ramsey theory for a triangle on FFF-free graphs

On tiling the integers with 444-sets of the same gap sequence

(1,k)(1, k)(1,k)-coloring of graphs with girth at least 555 on a surface

On Choosability with Separation of Planar Graphs with Forbidden Cycles

Toroidal graphs containing neither K5−K_5^{-}K5−​ nor 6-cycles are 4-choosable

Vertex Arboricity of Toroidal Graphs with a Forbidden Cycle

See the researcher in context

Building this map preview

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

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

Online Ramsey theory for a triangle on $F$ -free graphs

On tiling the integers with $4$ -sets of the same gap sequence

$(1, k)$ -coloring of graphs with girth at least $5$ on a surface

Toroidal graphs containing neither $K_5^{-}$ nor 6-cycles are 4-choosable