BZPEER

preprint2026arXiv

A sufficient condition for a hypergraph to have a Berge- $k$ -factor

For any graph (hypergraph) $G$ with vertex set $V$ and edge set $E$ , we define its incidence bipartite graph $\mathcal{I}(G)$ as the bipartite graph with bipartition $(E, V)$ , where an edge $e \in E$ is adjacent to a vertex $v \in V$ in $\mathcal{I}(G)$ if and only if $e$ is incident to $v$ in $G$ . This representation allows all concepts and properties of $G$ to be reformulated in terms of those of $\mathcal{I}(G)$ . In this paper, we investigate the notions of graph toughness and $k$ -factors in bipartite graphs through this incidence perspective. As an application, our result implies the classic theorem of Enomoto, Jackson, Katerinis, and Saito: for any integer $k \geq 1$ , a $k$ -tough graph $G$ has a $k$ -factor if $k |V(G)|$ is even and $|V(G)| \geq k+1$ . Furthermore, we extend this result to hypergraphs, without requiring uniformity.

preprint2022arXiv

1-planar graphs are odd 13-colorable

An odd coloring of a graph $G$ is a proper coloring such that any non-isolated vertex in $G$ has a coloring appears odd times on its neighbors. The odd chromatic number, denoted by $χ_o(G)$ , is the minimum number of colors that admits an odd coloring of $G$ . Petruševski and Škrekovski in 2021 introduced this notion and proved that if $G$ is planar, then $χ_o(G)\le9$ and conjectured that $χ_o(G)\le5$ . More recently, Petr and Portier improved $9$ to $8$ . A graph is $1$ -planar if it can be drawn in the plane so that each edge is crossed by at most one other edge. Cranston, Lafferty and Song showed that every $1$ -planar graph is odd $23$ -colorable. In this paper, we improved this result and showed that every $1$ -planar graph is odd $13$ -colorable.

preprint2022arXiv

Enhancing the Erdős-Lovász Tihany Conjecture for line graphs of multigraphs

In this paper, we prove an enhanced version of the Erdős-Lovász Tihany Conjecture for line graphs of multigraphs. That is, for every graph $G$ whose chromatic number $χ(G)$ is more than its clique number $ω(G)$ and for nonnegative integer $\ell$ , any two integers $s,t \geq 3.5\ell+2$ with $s+t = χ(G)+1$ , there is a partition $(S,T)$ of the vertex set $V(G)$ such that $χ(G[S])\geq s$ and $χ(G[T])\geq t+\ell$ . In particular, when $\ell=1$ , we can obtain the same result just for any $s,t\geq4$ . The Erdős-Lovász Tihany conjecture is a special case when $\ell=0$ .

preprint2022arXiv

Spanning tree packing and 2-essential edge-connectivity

An edge (vertex) cut $X$ of $G$ is $r$ -essential if $G-X$ has two components each of which has at least $r$ edges. A graph $G$ is $r$ -essentially $k$ -edge-connected (resp. $k$ -connected) if it has no $r$ -essential edge (resp. vertex) cuts of size less than $k$ . If $r=1$ , we simply call it essential. Recently, Lai and Li proved that every $m$ -edge-connected essentially $h$ -edge-connected graph contains $k$ edge-disjoint spanning trees, where $k,m,h$ are positive integers such that $k+1\le m\le 2k-1$ and $h\ge \frac{m^2}{m-k}-2$ . In this paper, we show that every $m$ -edge-connected and $2$ -essentially $h$ -edge-connected graph that is not a $K_5$ or a fat-triangle with multiplicity less than $k$ has $k$ edge-disjoint spanning trees, where $k+1\le m\le 2k-1$ and $h\ge f(m,k)=\begin{cases} 2m+k-4+\frac{k(2k-1)}{2m-2k-1}, & m< k+\frac{1+\sqrt{8k+1}}{4}, \\ m+3k-4+\frac{k^2}{m-k}, & m\ge k+\frac{1+\sqrt{8k+1}}{4}. \end{cases}$ Extending Zhan's result, we also prove that every 3-edge-connected essentially 5-edge-connected and $2$ -essentially 8-edge-connected graph has two edge-disjoint spanning trees. As an application, this gives a new sufficient condition for Hamilton-connectedness of line graphs. In 2012, Kaiser and Vrána proved that every 5-connected line graph of minimum degree at least 6 is Hamilton-connected. We allow graphs to have minimum degree 5 and prove that every 5-connected essentially 8-connected line graph is Hamilton-connected.

preprint2020arXiv

Enhancing the Erdős-Lovász Tihany Conjecture for graphs with independence number two

Let $s\ge2$ and $t\ge2$ be integers. A graph $G$ is $(s,t)$ -\emph{splittable} if $V(G)$ can be partitioned into two sets $S$ and $T$ such that $χ(G[S])\geq s$ and $χ(G[T])\geq t$ . The well-known Erdős-Lovász Tihany Conjecture from 1968 states that every graph $G$ whose chromatic number $χ(G)=s+t-1$ is more than its clique number $ω(G)$ is $(s,t)$ -splittable. In this paper, we prove an enhanced version of the Erdős-Lovász Tihany Conjecture for graphs with independence number two. That is, for every graph $G$ with $χ(G)=s+t-1>ω(G)+1$ is $(s,t+1)$ -splittable. There are examples showing that this result is best possible.

preprint2016arXiv

Equitable coloring of sparse planar graphs

A proper vertex coloring of a graph $G$ is equitable if the sizes of color classes differ by at most one. The equitable chromatic threshold $χ_{eq}^*(G)$ of $G$ is the smallest integer $m$ such that $G$ is equitably $n$ -colorable for all $n\ge m$ . We show that for planar graphs $G$ with minimum degree at least two, $χ_{eq}^*(G)\le 4$ if the girth of $G$ is at least $10$ , and $χ_{eq}^*(G)\le 3$ if the girth of $G$ is at least $14$ .

preprint2016arXiv

Extremal permutations in routing cycles

Let $G$ be a graph on $n$ vertices, labeled $v_1,\ldots,v_n$ and $π$ be a permutation on $[n]:=\{1,2,\cdots, n\}$ . Suppose that each pebble $p_i$ is placed at vertex $v_{π(i)}$ and has destination $v_i$ . During each step, a disjoint set of edges is selected and the pebbles on each edge are swapped. Let $rt(G, π)$ , the routing number for $π$ , be the minimum number of steps necessary for the pebbles to reach their destinations. Li, Lu, and Yang prove that $rt(C_n, π)\le n-1$ for any permutation on $n$ -cycle $C_n$ and conjecture that for $n \geq 5$ , if $rt(C_n, π) = n-1$ , then $π= (123\cdots n)$ or its inverse. By a computer search, they show that the conjecture holds for $n<8$ . We prove in this paper that the conjecture holds for all even $n$ .

preprint2015arXiv

A relaxation of the Bordeaux Conjecture

A $(c_1,c_2,...,c_k)$ -coloring of $G$ is a mapping $φ:V(G)\mapsto\{1,2,...,k\}$ such that for every $i,1 \leq i \leq k$ , $G[V_i]$ has maximum degree at most $c_i$ , where $G[V_i]$ denotes the subgraph induced by the vertices colored $i$ . Borodin and Raspaud conjecture that every planar graph without intersecting triangles and $5$ -cycles is $3$ -colorable. We prove in this paper that every planar graph without intersecting triangles and $5$ -cycles is (2,0,0)-colorable.

preprint2015arXiv

A relaxation of the strong Bordeaux Conjecture

Let $c_1, c_2, \cdots, c_k$ be $k$ non-negative integers. A graph $G$ is $(c_1, c_2, \cdots, c_k)$ -colorable if the vertex set can be partitioned into $k$ sets $V_1,V_2, \ldots, V_k$ , such that the subgraph $G[V_i]$ , induced by $V_i$ , has maximum degree at most $c_i$ for $i=1, 2, \ldots, k$ . Let $\mathcal{F}$ denote the family of plane graphs with neither adjacent 3-cycles nor $5$ -cycle. Borodin and Raspaud (2003) conjectured that each graph in $\mathcal{F}$ is $(0,0,0)$ -colorable. In this paper, we prove that each graph in $\mathcal{F}$ is $(1, 1, 0)$ -colorable, which improves the results by Xu (2009) and Liu-Li-Yu (2014+).

preprint2014arXiv

An Upper Bound on the Number of Circular Transpositions to Sort a Permutation

We consider the problem of upper bounding the number of circular transpositions needed to sort a permutation. It is well known that any permutation can be sorted using at most $n(n-1)/2$ adjacent transpositions. We show that, if we allow all adjacent transpositions, as well as the transposition that interchanges the element in position 1 with the element in the last position, then the number of transpositions needed is at most $n^2/4$ . This answers an open question posed by Feng, Chitturi and Sudborough (2010).

preprint2014arXiv

Optimal open-locating-dominating sets in infinite triangular grids

An open-locating-dominating set (OLD-set) is a subset of vertices of a graph such that every vertex in the graph has at least one neighbor in the set and no two vertices in the graph have the same set of neighbors in the set. This is an analogue to the well-studied identifying code in the literature. In this paper, we prove that the optimal density of the OLD-set for the infinite triangular grid is $4/13$ .

preprint2014arXiv

Planar graphs without 5-cycles and intersecting triangles are $(1,1,0)$ -colorable

A $(c_1,c_2,...,c_k)$ -coloring of $G$ is a mapping $φ:V(G)\mapsto\{1,2,...,k\}$ such that for every $i,1 \leq i \leq k$ , $G[V_i]$ has maximum degree at most $c_i$ , where $G[V_i]$ denotes the subgraph induced by the vertices colored $i$ . Borodin and Raspaud conjecture that every planar graph without $5$ -cycles and intersecting triangles is $(0,0,0)$ -colorable. We prove in this paper that such graphs are $(1,1,0)$ -colorable.

preprint2013arXiv

Strong edge-colorings for k-degenerate graphs

We prove that the strong chromatic index for each $k$ -degenerate graph with maximum degree $Δ$ is at most $(4k-2)Δ-k(2k-1)+1$ .

preprint2012arXiv

A relaxation of Steinberg's Conjecture

A graph is $(c_1, c_2, ..., c_k)$ -colorable if the vertex set can be partitioned into $k$ sets $V_1,V_2, ..., V_k$ , such that for every $i: 1\leq i\leq k$ the subgraph $G[V_i]$ has maximum degree at most $c_i$ . We show that every planar graph without 4- and 5-cycles is $(1, 1, 0)$ -colorable and $(3,0,0)$ -colorable. This is a relaxation of the Steinberg Conjecture that every planar graph without 4- and 5-cycles are properly 3-colorable (i.e., $(0,0,0)$ -colorable).

preprint2012arXiv

Perfect partition of some regular bipartite graphs

A graph has a perfect partition if all its perfect matchings can be partitioned so that each part is a 1-factorization of the graph. Let $L_{rm, r}=K_{rm,rm}-mK_{r,r}$ . We first give a formula to count the number of perfect matchings of $L_{rm, r}$ , then show that $L_{6,1}$ and $L_{8,2}$ have perfect partitions.

preprint2011arXiv

New Bounds on the Minimum Density of a Vertex Identifying Code for the Infinite Hexagonal Grid

For a graph, $G$ , and a vertex $v \in V(G)$ , let $N[v]$ be the set of vertices adjacent to and including $v$ . A set $D \subseteq V(G)$ is a vertex identifying code if for any two distinct vertices $v_1, v_2 \in V(G)$ , the vertex sets $N[v_1] \cap D$ and $N[v_2] \cap D$ are distinct and non-empty. We consider the minimum density of a vertex identifying code for the infinite hexagonal grid. In 2000, Cohen et al. constructed two codes with a density of $3/7 \approx 0.428571$ , and this remains the best known upper bound. Until now, the best known lower bound was $12/29 \approx 0.413793$ and was proved by Cranston and Yu in 2009. We present three new codes with a density of 3/7, and we improve the lower bound to $5/12 \approx 0.416667$ .

preprint2010arXiv

A New Lower Bound on the Density of Vertex Identifying Codes for the Infinite Hexagonal Grid

Given a graph $G$ , an identifying code $C \subseteq V(G)$ is a vertex set such that for any two distinct vertices $v_1,v_2\in V(G)$ , the sets $N[v_1]\cap C$ and $N[v_2]\cap C$ are distinct and nonempty (here $N[v]$ denotes a vertex $v$ and its neighbors). We study the case when $G$ is the infinite hexagonal grid $H$ . Cohen et.al. constructed two identifying codes for $H$ with density $3/7$ and proved that any identifying code for $H$ must have density at least $16/39\approx0.410256$ . Both their upper and lower bounds were best known until now. Here we prove a lower bound of $12/29\approx0.413793$ .

preprint2010arXiv

Injective colorings of graphs with low average degree

Let $\mad(G)$ denote the maximum average degree (over all subgraphs) of $G$ and let $χ_i(G)$ denote the injective chromatic number of $G$ . We prove that if $Δ\geq 4$ and $\mad(G)<\frac{14}5$, then $χ_i(G)\leqΔ+2$ . When $Δ=3$ , we show that $\mad(G)<\frac{36}{13}$ implies $χ_i(G)\le 5$ . In contrast, we give a graph $G$ with $Δ=3$ , $\mad(G)=\frac{36}{13}$, and $χ_i(G)=6$ .

preprint2010arXiv

Injective colorings of sparse graphs

Let $mad(G)$ denote the maximum average degree (over all subgraphs) of $G$ and let $χ_i(G)$ denote the injective chromatic number of $G$ . We prove that if $mad(G) \leq 5/2$ , then $χ_i(G)\leqΔ(G) + 1$ ; and if $mad(G) < 42/19$ , then $χ_i(G)=Δ(G)$ . Suppose that $G$ is a planar graph with girth $g(G)$ and $Δ(G)\geq 4$ . We prove that if $g(G)\geq 9$ , then $χ_i(G)\leqΔ(G)+1$ ; similarly, if $g(G)\geq 13$ , then $χ_i(G)=Δ(G)$ .

preprint2010arXiv

Linear Choosability of Sparse Graphs

We study the linear list chromatic number, denoted $\lcl(G)$, of sparse graphs. The maximum average degree of a graph $G$ , denoted $\mad(G)$, is the maximum of the average degrees of all subgraphs of $G$ . It is clear that any graph $G$ with maximum degree $Δ(G)$ satisfies $\lcl(G)\ge \ceil{Δ(G)/2}+1$. In this paper, we prove the following results: (1) if $\mad(G)<12/5$ and $Δ(G)\ge 3$ , then $\lcl(G)=\ceil{Δ(G)/2}+1$, and we give an infinite family of examples to show that this result is best possible; (2) if $\mad(G)<3$ and $Δ(G)\ge 9$ , then $\lcl(G)\le\ceil{Δ(G)/2}+2$, and we give an infinite family of examples to show that the bound on $\mad(G)$ cannot be increased in general; (3) if $G$ is planar and has girth at least 5, then $\lcl(G)\le\ceil{Δ(G)/2}+4$.

Gexin Yu

Research overview

Is this your work?

20 publications

A sufficient condition for a hypergraph to have a Berge- $k$ -factor

1-planar graphs are odd 13-colorable

Enhancing the Erdős-Lovász Tihany Conjecture for line graphs of multigraphs

Spanning tree packing and 2-essential edge-connectivity

Enhancing the Erdős-Lovász Tihany Conjecture for graphs with independence number two

Equitable coloring of sparse planar graphs

Extremal permutations in routing cycles

A relaxation of the Bordeaux Conjecture

A relaxation of the strong Bordeaux Conjecture

An Upper Bound on the Number of Circular Transpositions to Sort a Permutation

Optimal open-locating-dominating sets in infinite triangular grids

Planar graphs without 5-cycles and intersecting triangles are $(1,1,0)$ -colorable

Strong edge-colorings for k-degenerate graphs

A relaxation of Steinberg's Conjecture

Perfect partition of some regular bipartite graphs

New Bounds on the Minimum Density of a Vertex Identifying Code for the Infinite Hexagonal Grid

A New Lower Bound on the Density of Vertex Identifying Codes for the Infinite Hexagonal Grid

Injective colorings of graphs with low average degree

Injective colorings of sparse graphs

Linear Choosability of Sparse Graphs

See the researcher in context

Building this map preview

Gexin Yu

Research overview

Is this your work?

20 publications

A sufficient condition for a hypergraph to have a Berge-kkk-factor

1-planar graphs are odd 13-colorable

Enhancing the Erdős-Lovász Tihany Conjecture for line graphs of multigraphs

Spanning tree packing and 2-essential edge-connectivity

Enhancing the Erdős-Lovász Tihany Conjecture for graphs with independence number two

Equitable coloring of sparse planar graphs

Extremal permutations in routing cycles

A relaxation of the Bordeaux Conjecture

A relaxation of the strong Bordeaux Conjecture

An Upper Bound on the Number of Circular Transpositions to Sort a Permutation

Optimal open-locating-dominating sets in infinite triangular grids

Planar graphs without 5-cycles and intersecting triangles are (1,1,0)(1,1,0)(1,1,0)-colorable

Strong edge-colorings for k-degenerate graphs

A relaxation of Steinberg's Conjecture

Perfect partition of some regular bipartite graphs

New Bounds on the Minimum Density of a Vertex Identifying Code for the Infinite Hexagonal Grid

A New Lower Bound on the Density of Vertex Identifying Codes for the Infinite Hexagonal Grid

Injective colorings of graphs with low average degree

Injective colorings of sparse graphs

Linear Choosability of Sparse Graphs

See the researcher in context

Building this map preview

A sufficient condition for a hypergraph to have a Berge- $k$ -factor

Planar graphs without 5-cycles and intersecting triangles are $(1,1,0)$ -colorable