BZPEER

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

On toric ideals arising from signed graphs

A signed graph is a pair $(G,τ)$ of a graph $G$ and its sign $τ$ , where a \textit{sign} $τ$ is a function from $\{ (e,v)\mid e\in E(G),v\in V(G), v\in e\}$ to $\{1,-1\}$ . Note that graphs or digraphs are special cases of signed graphs. In this paper, we study the toric ideal $I_{(G,τ)}$ associated with a signed graph $(G,τ)$ , and the results of the paper give a unified idea to explain some known results on the toric ideals of a graph or a digraph. We characterize all primitive binomials of $I_{(G,τ)}$ , and then focus on the complete intersection property. More precisely, we find a complete list of graphs $G$ such that $I_{(G,τ)}$ is a complete intersection for every sign $τ$ .

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

Stable structure on safe set problems in vertex-weighted graphs

Let $G$ be a graph, and let $w$ be a positive real-valued weight function on $V(G)$ . For every subset $S$ of $V(G)$ , let $w(S)=\sum_{v \in S} w(v).$ A non-empty subset $S \subset V(G)$ is a weighted safe set of $(G,w)$ if, for every component $C$ of the subgraph induced by $S$ and every component $D$ of $G-S$ , we have $w(C) \geq w(D)$ whenever there is an edge between $C$ and $D$ . If the subgraph of $G$ induced by a weighted safe set $S$ is connected, then the set $S$ is called a connected weighted safe set of $(G,w)$ . The weighted safe number $\mathrm{s}(G,w)$ and connected weighted safe number $\mathrm{cs}(G,w)$ of $(G,w)$ are the minimum weights $w(S)$ among all weighted safe sets and all connected weighted safe sets of $(G,w)$ , respectively. Note that for every pair $(G,w)$ , $\mathrm{s}(G,w) \le \mathrm{cs}(G,w)$ by their definitions. Recently, it was asked which pair $(G,w)$ satisfies the equality and shown that every weighted cycle satisfies the equality. In this paper, we give a complete list of connected bipartite graphs $G$ such that $\mathrm{s}(G,w)=\mathrm{cs}(G,w)$ for every weight function $w$ on $V(G)$ .

preprint2020arXiv

The optimal proper connection number of a graph with given independence number

An edge-colored connected graph $G$ is properly connected if between every pair of distinct vertices, there exists a path that no two adjacent edges have a same color. Fujita (2019) introduced the optimal proper connection number ${\mathrm{pc}_{\mathrm{opt}}}(G)$ for a monochromatic connected graph $G$ , to make a connected graph properly connected efficiently. More precisely, ${\mathrm{pc}_{\mathrm{opt}}}(G)$ is the smallest integer $p+q$ when one converts a given monochromatic graph $G$ into a properly connected graph by recoloring $p$ edges with $q$ colors. In this paper, we show that ${\mathrm{pc}_{\mathrm{opt}}}(G)$ has an upper bound in terms of the independence number $α(G)$ . Namely, we prove that for a connected graph $G$ , ${\mathrm{pc}_{\mathrm{opt}}}(G)\le \frac{5α(G)-1}{2}$ . Moreoevr, for the case $α(G)\leq 3$ , we improve the upper bound to $4$ , which is tight.

preprint2020arXiv

The size of graphs with restricted rainbow $2$ -connection number

Let $k$ be a positive integer, and $G$ be a $k$ -connected graph. An edge-coloured path is \emph{rainbow} if all of its edges have distinct colours. The \emph{rainbow $k$ -connection number} of $G$ , denoted by $rc_k(G)$ , is the minimum number of colours in an edge-colouring of $G$ such that, any two vertices are connected by $k$ internally vertex-disjoint rainbow paths. The function $rc_k(G)$ was introduced by Chartrand, Johns, McKeon and Zhang in 2009, and has since attracted significant interest. Let $t_k(n,r)$ denote the minimum number of edges in a $k$ -connected graph $G$ on $n$ vertices with $rc_k(G)\le r$ . Let $s_k(n,r)$ denote the maximum number of edges in a $k$ -connected graph $G$ on $n$ vertices with $rc_k(G)\ge r$ . The functions $t_1(n,r)$ and $s_1(n,r)$ have previously been studied by various authors. In this paper, we study the functions $t_2(n,r)$ and $s_2(n,r)$ . We determine bounds for $t_2(n,r)$ which imply that $t_2(n,2)=(1+o(1))n\log_2 n$ , and $t_2(n,r)$ is linear in $n$ for $r\ge 3$ . We also provide some remarks about the function $s_2(n,r)$ .

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.

preprint2016arXiv

Cycles with two blocks in $k$ -chromatic digraphs

Let $k$ and $\ell$ be positive integers. A cycle with two blocks $c(k,\ell)$ is an oriented cycle which consists of two internally (vertex) disjoint directed paths of lengths at least $k$ and $\ell$ , respectively, from a vertex to another one. A problem of Addario-Berry, Havet and Thomassé (2007) asked if, given positive integers $k$ and $\ell$ such that $k+\ell\ge 4$ , any strongly connected digraph $D$ containing no $c(k,\ell)$ has chromatic number at most $k+\ell-1$ . In this paper, we show that such digraph $D$ has chromatic number at most $O((k+\ell)^2)$ , improving the previous upper bound $O((k+\ell)^4)$ obtained by Cohen, Havet, Lochet and Nisse (2016). In fact, we are able to find a digraph which shows that the answer to the above problem is no. We also show that if in addition $D$ is Hamiltonian, then its underlying simple graph is $(k+\ell-1)$ -degenerate and thus the chromatic number of $D$ is at most $k+\ell$ , which is tight.

preprint2016arXiv

Pseudograph and its associated real toric manifold

Given a simple graph $G$ , the graph associahedron $P_G$ is a convex polytope whose facets correspond to the connected induced subgraphs of $G$ . Graph associahedra have been studied widely and are found in a broad range of subjects. Recently, S. Choi and H. Park computed the rational Betti numbers of the real toric variety corresponding to a graph associahedron under the canonical Delzant realization. In this paper, we focus on a pseudograph associahedron which was introduced by Carr, Devadoss and Forcey, and then discuss how to compute the Poincaré polynomial of the real toric variety corresponding to a pseudograph associahedron under the canonical Delzant realization.

preprint2016arXiv

The Betti numbers of real toric varieties associated to Weyl chambers of type $B$

We compute the (rational) Betti number of real toric varieties associated to Weyl chambers of type $B$ . Furthermore, we show that their integral cohomology is $p$ -torsion free for all odd primes $p$ .

preprint2015arXiv

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

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 {\em maximum average degree} of $G$ , $mad (G)$ , is the maximum among the average degrees of the subgraphs of $G$ . It is known in \cite{BLP-14-JGT} that there is no constant $C$ such that every graph $G$ with $mad(G)< 4$ has $χ(G^2) \leq Δ(G) + C$ . Charpentier \cite{Charpentier14} conjectured that there exists an integer $D$ such that every graph $G$ with $Δ(G)\ge D$ and $mad(G)<4$ has $χ(G^2) \leq 2 Δ(G)$ . Recent result in \cite{BLP-DM} implies that $χ(G^2) \leq 2 Δ(G)$ if $mad(G) < 4 -\frac{1}{c}$ with $Δ(G) \geq 40c -16$ . In this paper, we show for $c\ge 2$ , if $mad(G) < 4 - \frac{1}{c}$ and $Δ(G) \geq 14c-7$ , then $χ_\ell(G^2) \leq 2 Δ(G)$ , which improves the result in \cite{BLP-DM}. We also show that for every integer $D$ , there is a graph $G$ with $Δ(G)\ge D$ such that $mad(G)<4$ , and $χ(G^2) \geq 2Δ(G) +2$ , which disproves Charpentier's conjecture. In addition, we give counterexamples to Charpentier's another conjecture in \cite{Charpentier14}, stating that for every integer $k\ge 3$ , there is an integer $D_k$ such that every graph $G$ with $mad(G)<2k$ and $Δ(G)\ge D_k$ has $χ(G^2) \leq kΔ(G) -k$ .

preprint2015arXiv

On the safe set of Cartesian product of two complete graphs

For a connected graph $G$ , a vertex subset $S$ of $V(G)$ is a safe set if for every component $C$ of the subgraph of $G$ induced by $S$ , $|C| \ge |D|$ holds for every component $D$ of $G-S$ such that there exists an edge between $C$ and $D$ , and, in particular, if the subgraph induced by $S$ is connected, then $S$ is called a connected safe set. For a connected graph $G$ , the safe number and the connected safe number of $G$ are the minimum among sizes of the safe sets and the minimum among sizes of the connected safe sets, respectively, of $G$ . Fujita et al. introduced these notions in connection with a variation of the facility location problem. In this paper, we study the safe number and the connected safe number of Cartesian product of two complete graphs. Figuring out a way to reduce the number of components to two without changing the size of safe set makes it sufficient to consider only partitions of an integer into two parts without which it would be much more complicated to take care of all the partitions. In this way, we could show that the safe number and the connected safe number of Cartesian product of two complete graphs are equal and present a polynomial-time algorithm to compute them. Especially, in the case where one of complete components has order at most four, we precisely formulate those numbers.

preprint2014arXiv

Bipartite graphs whose squares are not chromatic-choosable

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 $χ(H)$ and $χ_{\ell}(H)$ be the chromatic number and the list chromatic number of $H$ , respectively. A graph $H$ is called {\em chromatic-choosable} if $χ_{\ell} (H) = χ(H)$ . It is an interesting problem to find graphs that are chromatic-choosable. Motivated by the List Total Coloring Conjecture, Kostochka and Woodall (2001) proposed the List Square Coloring Conjecture which states that $G^2$ is chromatic-choosable for every graph $G$ . Recently, Kim and Park showed that the List Square Coloring Conjecture does not hold in general by finding a family of graphs whose squares are complete multipartite graphs with partite sets of unbounded size. It is a well-known fact that the List Total Coloring Conjecture is true if the List Square Coloring Conjecture holds for special class of bipartite graphs. On the other hand, the counterexamples to the List Square Coloring Conjecture are not bipartite graphs. Hence a natural question is whether $G^2$ is chromatic-choosable or not for every bipartite graph $G$ . In this paper, we give a bipartite graph $G$ such that $χ_{\ell} (G^2) \neq χ(G^2)$ . Moreover, we show that the value $χ_{\ell}(G^2) - χ(G^2)$ can be arbitrarily large.

preprint2014arXiv

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

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 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. Determining the chromatic number of the square of the Kneser graph $K(n, k)$ is an interesting graph coloring problem, and is also related with intersecting family problem. The square of $K(2k, k)$ is a perfect matching and the square of $K(n, k)$ is the complete graph when $n \geq 3k-1$ . Hence coloring of the square of $K(2k +1, k)$ has been studied as the first nontrivial case. In this paper, we focus on the question of determining $χ(K^2(2k+r,k))$ for $r \geq 2$ . Recently, Kim and Park \cite{KP2014} showed that $χ(K^2(2k+1,k)) \leq 2k+2$ if $2k +1 = 2^t -1$ for some positive integer $t$ . In this paper, we generalize the result by showing that for any integer $r$ with $1 \leq r \leq k -2$ , (a) $χ(K^2 (2k+r, k)) \leq (2k+r)^r$ , if $2k + r = 2^t$ for some integer $t$ , and (b) $χ(K^2 (2k+r, k)) \leq (2k+r+1)^r$ , if $2k + r = 2^t-1$ for some integer $t$ . On the other hand, it was showed in \cite{KP2014} that $χ(K^2 (2k+r, k)) \leq (r+2)(3k + \frac{3r+3}{2})^r$ for $2 \leq r \leq k-2$ . We improve these bounds by showing that for any integer $r$ with $2 \leq r \leq k -2$ , we have $χ(K^2 (2k+r, k)) \leq2 \left(\frac{9}{4}k + \frac{9(r+3)}{8} \right)^r$ . Our approach is also related with injective coloring and coloring of Johnson graph.

preprint2013arXiv

Chromatic-choosability of the power of graphs

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 $k$ . Let $χ(H)$ and $χ_l(H)$ be the chromatic number and the list chromatic number of $H$ , respectively. A graph $H$ is called {\em chromatic-choosable} if $χ_l (H) = χ(H)$ . It is an interesting problem to find graphs that are chromatic-choosable. A natural question raised by Xuding Zhu (2012) is whether there exists a constant integer $k$ such that $G^k$ is chromatic-choosable for every graph $G$ . Motivated by the List Total Coloring Conjecture, Kostochka and Woodall (2001) asked whether $G^2$ is chromatic-choosable for every graph $G$ . Kim and Park (2013) answered the Kostochka and Woodall's question in the negative by finding a family of graphs whose squares are complete multipartite graphs with partite sets of equal and unbounded size. In this paper, we answer Zhu's question by showing that for every integer $k \geq 2$ , there exists a graph $G$ such that $G^k$ is not chromatic-choosable. Moreover, for any fixed $k$ we show that the value $χ_l(G^k) - χ(G^k)$ can be arbitrarily large.

preprint2013arXiv

Counterexamples to the List Square Coloring Conjecture

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 $χ(H)$ and $χ_l(H)$ be the chromatic number and the list chromatic number of $H$ , respectively. A graph $H$ is called {\em chromatic-choosable} if $χ_l (H) = χ(H)$ . It is an interesting problem to find graphs that are chromatic-choosable. Kostochka and Woodall \cite{KW2001} conjectured that $χ_l(G^2) = χ(G^2)$ for every graph $G$ , which is called List Square Coloring Conjecture. In this paper, we give infinitely many counterexamples to the conjecture. Moreover, we show that the value $χ_l(G^2) - χ(G^2)$ can be arbitrary large.

preprint2013arXiv

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

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 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. Determining the chromatic number of the square of the Kneser graph $K(2k+1, k)$ is an interesting problem, but not much progress has been made. Kim and Nakprasit \cite{2004KN} showed that $χ(K^2(2k+1,k)) \leq 4k+2$ , and Chen, Lih, and Wu \cite{2009CLW} showed that $χ(K^2(2k+1,k)) \leq 3k+2$ for $k \geq 3$ . In this paper, we give improved upper bounds on $χ(K^2(2k+1,k))$ . We show that $χ(K^2(2k+1,k)) \leq 2k+2$ , if $2k +1 = 2^n -1$ for some positive integer $n$ . Also we show that $χ(K^2(2k+1,k)) \leq \frac{8}{3}k+\frac{20}{3}$ for every integer $k\ge 2$ . In addition to giving improved upper bounds, our proof is concise and can be easily understood by readers while the proof in \cite{2009CLW} is very complicated. Moreover, we show that $χ(K^2(2k+r,k))=Θ(k^r)$ for each integer $2 \leq r \leq k-2$ .

preprint2013arXiv

The phylogeny graphs of doubly partial orders

The competition graph of a doubly partial order is known to be an interval graph. The CCE graph and the niche graph of a doubly partial order are also known to be interval graphs if the graphs do not contain a cycle of length four and three as an induced subgraph, respectively. Phylogeny graphs are variant of competition graphs. The phylogeny graph $P(D)$ of a digraph $D$ is the (simple undirected) graph defined by $V(P(D)):=V(D)$ and $E(P(D)):=\{xy \mid N^+_D(x) \cap N^+_D(y) \neq \emptyset \} \cup \{xy \mid (x,y) \in A(D) \}$ , where $N^+_D(x):=\{v \in V(D) \mid (x,v) \in A(D)\}$ . In this note, we show that the phylogeny graph of a doubly partial order is an interval graph. We also show that, for any interval graph $G$ , there exists an interval graph $\tilde{G}$ such that $\tilde{G}$ contains the graph $G$ as an induced subgraph and that $\tilde{G}$ is the phylogeny graph of a doubly partial order.

preprint2012arXiv

Competitively tight graphs

The competition graph of a digraph $D$ is a (simple undirected) graph which has the same vertex set as $D$ and has an edge between two distinct vertices $x$ and $y$ if and only if there exists a vertex $v$ in $D$ such that $(x,v)$ and $(y,v)$ are arcs of $D$ . For any graph $G$ , $G$ together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number $k(G)$ of a graph $G$ is the smallest number of such isolated vertices. Computing the competition number of a graph is an NP-hard problem in general and has been one of the important research problems in the study of competition graphs. Opsut [1982] showed that the competition number of a graph $G$ is related to the edge clique cover number $θ_E(G)$ of the graph $G$ via $θ_E(G)-|V(G)|+2 \leq k(G) \leq θ_E(G)$ . We first show that for any positive integer $m$ satisfying $2 \leq m \leq |V(G)|$ , there exists a graph $G$ with $k(G)=θ_E(G)-|V(G)|+m$ and characterize a graph $G$ satisfying $k(G)=θ_E(G)$ . We then focus on what we call \emph{competitively tight graphs} $G$ which satisfy the lower bound, i.e., $k(G)=θ_E(G)-|V(G)|+2$ . We completely characterize the competitively tight graphs having at most two triangles. In addition, we provide a new upper bound for the competition number of a graph from which we derive a sufficient condition and a necessary condition for a graph to be competitively tight.

preprint2012arXiv

The competition hypergraphs of doubly partial orders

Since Cho and Kim (2005) showed that the competition graph of a doubly partial order is an interval graph, it has been actively studied whether or not the same phenomenon occurs for other variants of competition graph and interesting results have been obtained. Continuing in the same spirit, we study the competition hypergraph, an interesting variant of the competition graph, of a doubly partial order. Though it turns out that the competition hypergraph of a doubly partial order is not always interval, we completely characterize the competition hypergraphs of doubly partial orders which are interval.

preprint2012arXiv

The competition number of a generalized line graph is at most two

In 1982, Opsut showed that the competition number of a line graph is at most two and gave a necessary and sufficient condition for the competition number of a line graph being one. In this note, we generalize this result to the competition numbers of generalized line graphs, that is, we show that the competition number of a generalized line graph is at most two, and give necessary conditions and sufficient conditions for the competition number of a generalized line graph being one.

preprint2011arXiv

On the hypercompetition numbers of hypergraphs

The competition hypergraph $C{\cH}(D)$ of a digraph $D$ is the hypergraph such that the vertex set is the same as $D$ and $e \subseteq V(D)$ is a hyperedge if and only if $e$ contains at least 2 vertices and $e$ coincides with the in-neighborhood of some vertex $v$ in the digraph $D$ . Any hypergraph with sufficiently many isolated vertices is the competition hypergraph of an acyclic digraph. The hypercompetition number $hk(\cH)$ of a hypergraph $\cH$ is defined to be the smallest number of such isolated vertices. In this paper, we study the hypercompetition numbers of hypergraphs. First, we give two lower bounds for the hypercompetition numbers which hold for any hypergraphs. And then, by using these results, we give the exact hypercompetition numbers for some family of uniform hypergraphs. In particular, we give the exact value of the hypercompetition number of a connected graph.

preprint2011arXiv

The competition number of a graph and the dimension of its hole space

The competition graph of a digraph D is a (simple undirected) 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 such that (x,v) and (y,v) are arcs of D. For any graph G, G together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number k(G) of G is the smallest number of such isolated vertices. In general, it is hard to compute the competition number k(G) for a graph G and it has been one of important research problems in the study of competition graphs to characterize a graph by its competition number. Recently, the relationship between the competition number and the number of holes of a graph is being studied. A hole of a graph is a cycle of length at least 4 as an induced subgraph. In this paper, we conjecture that the dimension of the hole space of a graph is no smaller than the competition number of the graph. We verify this conjecture for various kinds of graphs and show that our conjectured inequality is indeed an equality for connected triangle-free graphs.

preprint2011arXiv

The competition numbers of ternary Hamming graphs

It is known to be a hard problem to compute the competition number k(G) of a graph G in general. Park and Sano [13] gave the exact values of the competition numbers of Hamming graphs H(n,q) if $1 \leq n \leq 3$ or $1 \leq q \leq 2$ . In this paper, we give an explicit formula of the competition numbers of ternary Hamming graphs.

preprint2010arXiv

The competition numbers of Hamming graphs with diameter at most three

The competition graph of a digraph 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 such that (x,v) and (y,v) are arcs of D. For any graph G, G together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number k(G) of a graph G is defined to be the smallest number of such isolated vertices. In general, it is hard to compute the competition number k(G) for a graph G and it has been one of important research problems in the study of competition graphs. In this paper, we compute the competition numbers of Hamming graphs with diameter at most three.

Boram Park

Research overview

Is this your work?

27 publications

Proper conflict-free coloring of sparse graphs

Decomposing planar graphs into graphs with degree restrictions

Generalized list colouring of graphs

On toric ideals arising from signed graphs

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

Stable structure on safe set problems in vertex-weighted graphs

The optimal proper connection number of a graph with given independence number

The size of graphs with restricted rainbow $2$ -connection number

The strong clique number of graphs with forbidden cycles

Cycles with two blocks in $k$ -chromatic digraphs

Pseudograph and its associated real toric manifold

The Betti numbers of real toric varieties associated to Weyl chambers of type $B$

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

On the safe set of Cartesian product of two complete graphs

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

The phylogeny graphs of doubly partial orders

Competitively tight graphs

The competition hypergraphs of doubly partial orders

The competition number of a generalized line graph is at most two

On the hypercompetition numbers of hypergraphs

The competition number of a graph and the dimension of its hole space

The competition numbers of ternary Hamming graphs

The competition numbers of Hamming graphs with diameter at most three

See the researcher in context

Building this map preview

Boram Park

Research overview

Is this your work?

27 publications

Proper conflict-free coloring of sparse graphs

Decomposing planar graphs into graphs with degree restrictions

Generalized list colouring of graphs

On toric ideals arising from signed graphs

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

Stable structure on safe set problems in vertex-weighted graphs

The optimal proper connection number of a graph with given independence number

The size of graphs with restricted rainbow 222-connection number

The strong clique number of graphs with forbidden cycles

Cycles with two blocks in kkk-chromatic digraphs

Pseudograph and its associated real toric manifold

The Betti numbers of real toric varieties associated to Weyl chambers of type BBB

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

On the safe set of Cartesian product of two complete graphs

Bipartite graphs whose squares are not chromatic-choosable

Coloring of the square of Kneser graph K(2k+r,k)K(2k+r,k)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

The phylogeny graphs of doubly partial orders

Competitively tight graphs

The competition hypergraphs of doubly partial orders

The competition number of a generalized line graph is at most two

On the hypercompetition numbers of hypergraphs

The competition number of a graph and the dimension of its hole space

The competition numbers of ternary Hamming graphs

The competition numbers of Hamming graphs with diameter at most three

See the researcher in context

Building this map preview

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

The size of graphs with restricted rainbow $2$ -connection number

Cycles with two blocks in $k$ -chromatic digraphs

The Betti numbers of real toric varieties associated to Weyl chambers of type $B$

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