Xingxing Yu

activity

20152026

most citedA better bound on the size of rainbow matchings

9 citations · 39 across the 35 of their papers we have counts for

collaborators

36 papers

math.CO2026

Strong chromatic index of bipartite graphs

Yanli Hao, Tianchi Yang, Xingxing Yu

An edge-coloring of a graph $G$ is called a strong edge-coloring if all its color classes are induced matchings in $G$ ; the minimum number of colors required for such a coloring, d…

math.CO2023

A class of trees determined by their chromatic symmetric functions

Yuzhenni Wang, Xingxing Yu, Xiao-Dong Zhang

Stanley introduced the concept of chromatic symmetric functions of graphs which extends and refines the notion of chromatic polynomials of graphs, and asked whether trees are deter…

math.CO2023★ 1 cited

Planar Turán number of the 7-cycle

Ruilin Shi, Zach Walsh, Xingxing Yu

The $planar Tur a ˊ n number$ $ex_{P} (n, H)$ of a graph $H$ is the maximum number of edges in an $n$ -vertex planar graph without $H$ as a subgraph. Let $C_{\e…

math.CO2023

Linkages and removable paths avoiding vertices

Xiying Du, Yanjia Li, Shijie Xie +1

We say that a graph $G$ is $(2, m)$ -linked if, for any distinct vertices $a_{1}, \dots, a_{m}, b_{1}, b_{2}$ in $G$ , there exist vertex disjoint connected subgraphs $A, B$ of $G$ such that $\…

math.CO2023

On stability of rainbow matchings

Hongliang Lu, Yan Wang, Xingxing Yu

We show that for any integer $k \geq 1$ there exists an integer $t_{0} (k)$ such that for integers $t, k_{1}, \dots, k_{t + 1}, n$ with $t > t_{0} (k)$ , $max {k_{1}, \dots, k_{t + 1}} \leq k$ , and…

math.CO2021

Approximating TSP walks in subcubic graphs

Michael C. Wigal, Youngho Yoo, Xingxing Yu

We prove that every simple 2-connected subcubic graph on $n$ vertices with $n_{2}$ vertices of degree 2 has a TSP walk of length at most $\frac{5 n + n _{2}}{4} - 1$ , confirming a conjecture…

math.CO2021

On the 3-colorability of triangle-free and fork-free graphs

Joshua Schroeder, Zhiyu Wang, Xingxing Yu

A graph $G$ is said to satisfy the Vizing bound if $χ (G) \leq ω (G) + 1$ , where $χ (G)$ and $ω (G)$ denote the chromatic number and clique number of $G$ , respectively. It was conjectured…

math.CO2021

Co-degree threshold for rainbow perfect matchings in uniform hypergraphs

Hongliang Lu, Yan Wang, Xingxing Yu

Let $k$ and $n$ be two integers, with $k \geq 3$ , $n \equiv 0 (mod k)$ , and $n$ sufficiently large. We determine the $(k - 1)$ -degree threshold for the existence of a rainbow perfect ma…

math.CO2021

On Tutte cycles containing three prescribed edges

Michael C. Wigal, Xingxing Yu

A cycle $C$ in a graph $G$ is called a Tutte cycle if, after deleting $C$ from $G$ , each component has at most three neighbors on $C$ . Tutte cycles play an important role in the st…

math.CO2021★ 3 cited

Polynomial $χ$ -binding functions for $t$ -broom-free graphs

Xiaonan Liu, Joshua Schroeder, Zhiyu Wang +1

For any positive integer $t$ , a \emph{ $t$ -broom} is a graph obtained from $K_{1, t + 1}$ by subdividing an edge once. In this paper, we show that, for graphs $G$ without induced $t$ -b…

math.CO2021★ 1 cited

Rainbow perfect matchings for 4-uniform hypergraphs

Hongliang Lu, Yan Wang, Xingxing Yu

Let $n$ be a sufficiently large integer with $n \equiv 0 (mod 4)$ and let $F_{i} \subseteq (4 [ n ])$ where $i \in [n /4]$ . We show that if each vertex of $F_{i}$ is contained in more…

math.CO2021

Counting Hamiltonian cycles in planar triangulations

Xiaonan Liu, Zhiyu Wang, Xingxing Yu

Hakimi, Schmeichel, and Thomassen in 1979 conjectured that every $4$ -connected planar triangulation $G$ on $n$ vertices has at least $2 (n - 2) (n - 4)$ Hamiltonian cycles, with equality…

math.CO2021★ 1 cited

Number of Hamiltonian cycles in planar triangulations

Xiaonan Liu, Xingxing Yu

Whitney proved in 1931 that 4-connected planar triangulations are Hamiltonian. Hakimi, Schmeichel, and Thomassen conjectured in 1979 that if $G$ is a 4-connected planar triangulati…

math.CO2021

A note on exact minimum degree threshold for fractional perfect matchings

Hongliang Lu, Xingxing Yu

Rödl, Ruciński, and Szemerédi determined the minimum $(k - 1)$ -degree threshold for the existence of fractional perfect matchings in $k$ -uniform hypergrahs, and Kühn, Osthus, and Tow…

math.CO2020★ 5 cited

On the rainbow matching conjecture for 3-uniform hypergraphs

Jun Gao, Hongliang Lu, Jie Ma +1

Aharoni and Howard, and, independently, Huang, Loh, and Sudakov proposed the following rainbow version of Erdős matching conjecture: For positive integers $n, k, m$ with $n \geq k m$ , i…

math.CO2020

Partitioning digraphs with outdegree at least 4

Guanwu Liu, Xingxing Yu

Scott asked the question of determining $c_{d}$ such that if $D$ is a digraph with $m$ arcs and minimum outdegree $d \geq 2$ then $V (D)$ has a partition $V_{1}, V_{2}$ such that $\min\left…

math.CO2020

Rainbow matchings for 3-uniform hypergraphs

Hongliang Lu, Xingxing Yu, Xiaofan Yuan

Kühn, Osthus, and Treglown and, independently, Khan proved that if $H$ is a $3$ -uniform hypergraph with $n$ vertices such that $n \in 3 Z$ and large, and $δ_1(H)>{n-1\choose…

math.CO2020

4-Separations in Hajós Graphs

Qiqin Xie, Shijie Xie, Xiaofan Yuan +1

As a natural extension of the Four Color Theorem, Hajós conjectured that graphs containing no $K_{5}$ -subdivision are 4-colorable. Any possible counterexample to this conjecture with…

math.CO2020★ 9 cited

A better bound on the size of rainbow matchings

Hongliang Lu, Yan Wang, Xingxing Yu

Aharoni and Howard conjectured that, for positive integers $n, k, t$ with $n \geq k$ and $n \geq t$ , if $F_{1}, \dots, F_{t} \subseteq (k [ n ])$ such that $|F_i|>{n\choose k}-{n-t+1\cho…

math.CO2020★ 1 cited

Large cycles in essentially 4-connected graphs

Michael Wigal, Xingxing Yu

Tutte proved that every 4-connected planar graph contains a Hamilton cycle, but there are 3-connected $n$ -vertex planar graphs whose longest cycles have length $Θ (n^{l o g_{3} 2})$ . On…

math.CO2019

Monochromatic subgraphs in iterated triangulations

Jie Ma, Tianyun Tang, Xingxing Yu

For integers $n \geq 0$ , an iterated triangulation $T r (n)$ is defined recursively as follows: $T r (0)$ is the plane triangulation on three vertices and, for $n \geq 1$ , $T r (n)$ is the p…

math.CO2019

Wheels in planar graphs and Hajós graphs

Qiqin Xie, Shijie Xie, Xingxing Yu +1

It was conjectured by Hajós that graphs containing no $K_{5}$ -subdivision are 4-colorable. Previous results show that any possible minimum counterexample to Hajós' conjecture, called…

math.CO2019★ 2 cited

Near perfect matchings in uniform hypergraphs

Hongliang Lu, Xingxing Yu, Xiaofan Yuan

In this paper, we study degree conditions for the existence of large matchings in uniform hypergraphs. We prove that for integers $k, l, n$ with $k \geq 3$ , $k /2 < l < k$ , and $n$ large, i…

math.CO2018★ 6 cited

7-Connected Graphs are 4-Ordered

Rose McCarty, Yan Wang, Xingxing Yu

A graph $G$ is $k$ -ordered if for any distinct vertices $v_{1}, v_{2}, \dots, v_{k} \in V (G)$ , it has a cycle through $v_{1}, v_{2}, \dots, v_{k}$ in order. Let $f (k)$ denote the minimum int…

Strong chromatic index of bipartite graphs

A class of trees determined by their chromatic symmetric functions

Planar Turán number of the 7-cycle

Linkages and removable paths avoiding vertices

On stability of rainbow matchings

Approximating TSP walks in subcubic graphs

On the 3-colorability of triangle-free and fork-free graphs

Co-degree threshold for rainbow perfect matchings in uniform hypergraphs

On Tutte cycles containing three prescribed edges

Polynomial χ-binding functions for t-broom-free graphs

Rainbow perfect matchings for 4-uniform hypergraphs

Counting Hamiltonian cycles in planar triangulations

Number of Hamiltonian cycles in planar triangulations

A note on exact minimum degree threshold for fractional perfect matchings

On the rainbow matching conjecture for 3-uniform hypergraphs

Partitioning digraphs with outdegree at least 4

Rainbow matchings for 3-uniform hypergraphs

4-Separations in Hajós Graphs

A better bound on the size of rainbow matchings

Large cycles in essentially 4-connected graphs

Monochromatic subgraphs in iterated triangulations

Wheels in planar graphs and Hajós graphs

Near perfect matchings in uniform hypergraphs

7-Connected Graphs are 4-Ordered

Polynomial $χ$ -binding functions for $t$ -broom-free graphs