Zi-Xia Song

activity

20152026

most citedBreaking the degeneracy barrier for coloring graphs with no

K_{t}

minor

24 citations · 111 across the 46 of their papers we have counts for

collaborators

47 papers

math.CO2026

Positively Lin-Lu-Yau curved graphs with no $K_{2, t}$ minor

Shuliang Bai, Xiaonan Liu, Zi-Xia Song

Let $G$ be a connected graph with minimum degree at least two, positive Lin-Lu-Yau Ricci curvature, and no $K_{2, t}$ minor, where $t \geq 3$ is an integer. We first establish tight u…

math.CO2026

On the size of $(K_{t_{1}}, \dots, K_{t_{k}})$ -co-critical graphs

Zi-Xia Song

Given integers $k \geq 2$ and $t_{1}, \dots, t_{k} \geq 2$ , we write \emph{ $G \to (K_{t_{1}}, \dots, K_{t_{k}})$ } if every $k$ -coloring of the edges of a graph $G$ contains a monochrom…

math.CO2026

The Erdős-Lovász Tihany Conjecture holds for all even-hole-free graphs

Zi-Xia Song

Let $s, t \geq 2$ be integers. A graph $G$ is $(s, t)$ -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 Erdős-Lov…

math.CO2025

Dominating Hadwiger's Conjecture for graphs $G$ with $α (G) = 2$

Michael Scully, Zi-Xia Song

Hadwiger's Conjecture from 1943 states that every graph with chromatic number $t$ contains a $K_{t}$ minor. Illingworth and Wood [arXiv:2405.14299] introduced the concept of a ``domi…

math.CO2025

Dominating Hadwiger's Conjecture holds for all $2 K_{2}$ -free graphs

Zi-Xia Song, Thomas Tibbetts

A dominating $K_{t}$ minor in a graph $G$ is a sequence $(T_{1}, \dots, T_{t})$ of pairwise disjoint non-empty connected subgraphs of $G$ , such that for $1 \leq i < j \leq t$ , every vertex in…

math.CO2025

Odd clique minors in graphs with independence number two

Yuqing Ji, Zi-Xia Song, Evan Weiss +1

A $K_{t}$ -expansion consists of $t$ vertex-disjoint trees, every two of which are joined by an edge. We call such an expansion odd if its vertices can be two-colored so that the edge…

math.CO2024

On tight $(k, ℓ)$ -stable graphs

Xiaonan Liu, Zi-Xia Song, Zhiyu Wang

For integers $k > ℓ \geq 0$ , a graph $G$ is $(k, ℓ)$ -stable if $α (G - S) \geq α (G) - ℓ$ for every $S \subseteq V (G)$ with $∣ S ∣ = k$ . A recent result of Dong and Wu [SIAM J. Discrete Mat…

math.CO2023

Multicolor bipartite Ramsey number of double stars

Gregory DeCamillis, Zi-Xia Song

For positive integers $n, m$ , the double star $S (n, m)$ is the graph consisting of the disjoint union of two stars $K_{1, n}$ and $K_{1, m}$ together with an edge joining their center…

math.CO2023

The minimum degree of $(K_{s}, K_{t})$ -co-critical graphs

Ivan Casas-Rocha, Benjamin Snyder, Zi-Xia Song

Given graphs $G, H_{1}, H_{2}$ , we write $G \to (H_{1}, H_{2})$ if every {red, blue}-coloring of the edges of $G$ contains a red copy of $H_{1}$ or a blue copy of $H_{2}$ . A non-comp…

math.CO2023

Minimizing the number of edges in $(C_{4}, K_{1, k})$ -co-critical graphs

Gang Chen, Chenchen Ren, Zi-Xia Song

Given graphs $H_{1}, H_{2}$ , a {red, blue}-coloring of the edges of a graph $G$ is a critical coloring if $G$ has neither a red $H_{1}$ nor a blue $H_{2}$ . A non-complete graph $G$ is $(H…

math.CO2022

Multicolor Ramsey Number for Double Stars

Jake Ruotolo, Zi-Xia Song

For a graph $H$ and an integer $k \geq 1$ , let $r (H; k)$ and $r_{ℓ} (H; k)$ denote the $k$ -color Ramsey number and list Ramsey number of $H$ , respectively. Alon, Bucić, Kalvari, Kuperwa…

math.CO2022

Every graph with no $K_{9}^{- 6}$ minor is $8$ -colorable

Michael Lafferty, Zi-Xia Song

For positive integers $t$ and $s$ , let $K_{t}^{- s}$ denote the family of graphs obtained from the complete graph $K_{t}$ by removing $s$ edges. A graph $G$ has no $\mathcal{K…

math.CO2022★ 2 cited

An improved lower bound for the planar Turán number of cycles

Yongxin Lan, Zi-Xia Song

The planar Turán number of a graph $H$ , denoted by $e x_{_{P}} (n, H)$ , is the largest number of edges in a planar graph on $n$ vertices without containing $H$ as a subgraph.…

math.CO2022

Every graph with no $K_{8}^{- 4}$ minor is $7$ -colorable

Michael Lafferty, Zi-Xia Song

Hadwiger's Conjecture from 1943 states that every graph with no $K_{t}$ minor is $(t - 1)$ -colorable; it remains wide open for all $t \geq 7$ . For positive integers $t$ and $s$ , let $\…

math.CO2022

Properties of $8$ -contraction-critical graphs with no $K_{7}$ minor

Martin Rolek, Zi-Xia Song, Robin Thomas

Motivated by the famous Hadwiger's Conjecture, we study the properties of $8$ -contraction-critical graphs with no $K_{7}$ minor; we prove that every $8$ -contraction-critical graph wi…

math.CO2022★ 22 cited

A Note on Odd Colorings of 1-Planar Graphs

Daniel W. Cranston, Michael Lafferty, Zi-Xia Song

A proper coloring of a graph is odd if every non-isolated vertex has some color that appears an odd number of times on its neighborhood. This notion was recently introduced by Petr…

math.CO2022

Planar Turán numbers of cubic graphs and disjoint union of cycles

Yongxin Lan, Yongtang Shi, Zi-Xia Song

The planar Turán number of a graph $H$ , denoted $e x_{_{P}} (n, H)$ , is the maximum number of edges in a planar graph on $n$ vertices without containing $H$ as a subgraph. Thi…

math.CO2021

On the size of special class 1 graphs and $(P_{3}; k)$ -co-critical graphs

Gang Chen, Zhengke Miao, Zi-Xia Song +1

A well-known theorem of Vizing states that if $G$ is a simple graph with maximum degree $Δ$ , then the chromatic index $χ^{'} (G)$ of $G$ is $Δ$ or $Δ + 1$ . A graph $G$ is class 1 if $χ'(…

math.CO2021

Some remarks on even-hole-free graphs

Zi-Xia Song

A vertex of a graph is bisimplicial if the set of its neighbors is the union of two cliques; a graph is quasi-line if every vertex is bisimplicial. A recent result of Chudnovsky an…

math.CO2021

On the size of $(K_{t}, K_{1, k})$ -co-critical graphs

Hunter Davenport, Zi-Xia Song, Fan Yang

Given graphs $G, H_{1}, H_{2}$ , we write $G \to (H_{1}, H_{2})$ if every ${$ red, blue $}$ -coloring of the edges of $G$ contains a red copy of $H_{1}$ or a blue copy of $H_{2}$ . A no…

math.CO2019★ 8 cited

A new upper bound on the chromatic number of graphs with no odd $K_{t}$ minor

Sergey Norin, Zi-Xia Song

Gerards and Seymour conjectured that every graph with no odd $K_{t}$ minor is $(t - 1)$ -colorable. This is a strengthening of the famous Hadwiger's Conjecture. Geelen et al. proved tha…

math.CO2019★ 24 cited

Breaking the degeneracy barrier for coloring graphs with no $K_{t}$ minor

Sergey Norin, Luke Postle, Zi-Xia Song

In 1943, Hadwiger conjectured that every graph with no $K_{t}$ minor is $(t - 1)$ -colorable for every $t \geq 1$ . In the 1980s, Kostochka and Thomason independently proved that every gr…

math.CO2019★ 1 cited

Antimagic orientations of graphs with given independence number

Zi-Xia Song, Donglei Yang, Fangfang Zhang

Given a digraph $D$ with $m$ arcs and a bijection $τ : A (D) \to {1, 2, \dots, m}$ , we say $(D, τ)$ is an antimagic orientation of a graph $G$ if $D$ is an orientation of $…

math.CO2019★ 3 cited

Antimagic orientations of graphs with large maximum degree

Donglei Yang, Joshua Carlson, Andrew Owens +5

Given a digraph $D$ with $m$ arcs, a bijection $τ : A (D) \to {1, 2, \dots, m}$ is an antimagic labeling of $D$ if no two vertices in $D$ have the same vertex-sum, where t…

Positively Lin-Lu-Yau curved graphs with no K2,t​ minor

On the size of (Kt1​​,…,Ktk​​)-co-critical graphs

The Erdős-Lovász Tihany Conjecture holds for all even-hole-free graphs

Dominating Hadwiger's Conjecture for graphs G with α(G)=2

Dominating Hadwiger's Conjecture holds for all 2K2​-free graphs

Odd clique minors in graphs with independence number two

On tight (k,ℓ)-stable graphs

Multicolor bipartite Ramsey number of double stars

The minimum degree of (Ks​,Kt​)-co-critical graphs

Minimizing the number of edges in (C4​,K1,k​)-co-critical graphs

Multicolor Ramsey Number for Double Stars

Every graph with no K9−6​ minor is 8-colorable

An improved lower bound for the planar Turán number of cycles

Every graph with no K8−4​ minor is 7-colorable

Properties of 8-contraction-critical graphs with no K7​ minor

A Note on Odd Colorings of 1-Planar Graphs

Planar Turán numbers of cubic graphs and disjoint union of cycles

On the size of special class 1 graphs and (P3​;k)-co-critical graphs

Some remarks on even-hole-free graphs

On the size of (Kt​,K1,k​)-co-critical graphs

A new upper bound on the chromatic number of graphs with no odd Kt​ minor

Breaking the degeneracy barrier for coloring graphs with no Kt​ minor

Antimagic orientations of graphs with given independence number

Antimagic orientations of graphs with large maximum degree

Positively Lin-Lu-Yau curved graphs with no $K_{2, t}$ minor

On the size of $(K_{t_{1}}, \dots, K_{t_{k}})$ -co-critical graphs

Dominating Hadwiger's Conjecture for graphs $G$ with $α (G) = 2$

Dominating Hadwiger's Conjecture holds for all $2 K_{2}$ -free graphs

On tight $(k, ℓ)$ -stable graphs

The minimum degree of $(K_{s}, K_{t})$ -co-critical graphs

Minimizing the number of edges in $(C_{4}, K_{1, k})$ -co-critical graphs

Every graph with no $K_{9}^{- 6}$ minor is $8$ -colorable

Every graph with no $K_{8}^{- 4}$ minor is $7$ -colorable

Properties of $8$ -contraction-critical graphs with no $K_{7}$ minor

On the size of special class 1 graphs and $(P_{3}; k)$ -co-critical graphs

On the size of $(K_{t}, K_{1, k})$ -co-critical graphs

A new upper bound on the chromatic number of graphs with no odd $K_{t}$ minor

Breaking the degeneracy barrier for coloring graphs with no $K_{t}$ minor