BZPEER

preprint2022arXiv

Every graph with no $\mathcal{K}_8^{-4}$ minor is $7$ -colorable

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\ge 7$ . For positive integers $t$ and $s$ , let $\mathcal{K}_t^{-s}$ denote the family of graphs obtained from the complete graph $K_t$ by removing $s$ edges. We say that a graph $G$ has no $\mathcal{K}_t^{-s}$ minor if it has no $H$ minor for every $H\in \mathcal{K}_t^{-s}$ . Jakobsen in 1971 proved that every graph with no $\mathcal{K}_7^{-2}$ minor is $6$ -colorable. In this paper we consider the next step and prove that every graph with no $\mathcal{K}_8^{-4}$ minor is $7$ -colorable. Our result implies that $H$ -Hadwiger's Conjecture, suggested by Paul Seymour in 2017, is true for every graph $H$ on eight vertices such that the complement of $H$ has maximum degree at least four, a perfect matching, a triangle and a cycle of length four. Our proof utilizes an extremal function for $\mathcal{K}_8^{-4}$ minors obtained in this paper, generalized Kempe chains of contraction-critical graphs by Rolek and the second author, and the method for finding $K_7$ minors from three different $K_5$ subgraphs by Kawarabayashi and Toft; this method was first developed by Robertson, Seymour and Thomas in 1993 to prove Hadwiger's Conjecture for $t=6$ .

preprint2022arXiv

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

The planar Turán number of a graph $H$ , denoted $ex_{_\mathcal{P}}(n,H)$ , is the maximum number of edges in a planar graph on $n$ vertices without containing $H$ as a subgraph. This notion was introduced by Dowden in 2016 and has attracted quite some attention since then; those work mainly focus on finding $ex_{_\mathcal{P}}(n,H)$ when $H$ is a cycle or Theta graph or $H$ has maximum degree at least four. In this paper, we study $ex_{_\mathcal{P}}(n,H)$ when $H$ is a cubic graph or disjoint union of cycles or $H=K_{s, t}$ .

preprint2022arXiv

Properties of $8$ -contraction-critical graphs with no $K_7$ minor

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 with no $K_7$ minor has at most one vertex of degree $8$ , where a graph $G$ is $8$ -contraction-critical if $G$ is not $7$ -colorable but every proper minor of $G$ is $7$ -colorable. This is one step in our effort to prove that every graph with no $K_7$ minor is $7$ -colorable, which remains open.

preprint2020arXiv

Breaking the degeneracy barrier for coloring graphs with no $K_t$ minor

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 graph with no $K_t$ minor has average degree $O(t\sqrt{\log t})$ and hence is $O(t\sqrt{\log t})$ -colorable. We show that every graph with no $K_t$ minor is $O(t(\log t)^β)$ -colorable for every $β> 1/4$ , making the first improvement on the order of magnitude of the Kostochka-Thomason bound.

preprint2020arXiv

Gallai-Ramsey number of even cycles with chords

For a graph $H$ and an integer $k\ge1$ , the $k$ -color Ramsey number $R_k(H)$ is the least integer $N$ such that every $k$ -coloring of the edges of the complete graph $K_N$ contains a monochromatic copy of $H$ . Let $C_m$ denote the cycle on $m\ge4$ vertices and let $Θ_m$ denote the family of graphs obtained from $C_m$ by adding an additional edge joining two non-consecutive vertices. Unlike Ramsey number of odd cycles, little is known about the general behavior of $R_k(C_{2n})$ except that $R_k(C_{2n})\ge (n-1)k+n+k-1$ for all $k\ge2$ and $n\ge2$ . In this paper, we study Ramsey number of even cycles with chords under Gallai colorings, where a Gallai coloring is a coloring of the edges of a complete graph without rainbow triangles. For an integer $k\geq 1$ , the Gallai-Ramsey number $GR_k(H)$ of a graph $H$ is the least positive integer $N$ such that every Gallai $k$ -coloring of the complete graph $K_N$ contains a monochromatic copy of $H$ . We prove that $GR_k(Θ_{2n})=(n-1)k+n+1$ for all $k\geq 2$ and $n\geq 3$ . This implies that $GR_k(C_{2n})=(n-1)k+n+1$ all $k\geq 2$ and $n\geq 3$ . Our result yields a unified proof for the Gallai-Ramsey number of all even cycles on at least four vertices.

preprint2020arXiv

Gallai-Ramsey number of odd cycles with chords

A Gallai coloring is a coloring of the edges of a complete graph without rainbow triangles, and a Gallai $k$ -coloring is a Gallai coloring that uses at most $k$ colors. For an integer $k\geq 1$ , the Gallai-Ramsey number $GR_k(H)$ of a given graph $H$ is the least positive integer $N$ such that every Gallai $k$ -coloring of the complete graph $K_N$ contains a monochromatic copy of $H$ . Let $C_m$ denote the cycle on $m\ge4$ vertices and let $Θ_m$ denote the family of graphs obtained from $C_m$ by adding an additional edge joining two non-consecutive vertices. We prove that $GR_k(Θ_{2n+1})=n\cdot 2^k+1$ for all $k\geq 1$ and $n\geq 3$ . This implies that $GR_k(C_{2n+1})=n\cdot 2^k+1$ all $k\geq 1$ and $n\geq 3$ . Our result yields a unified proof for the Gallai-Ramsey number of all odd cycles on at least five vertices.

preprint2020arXiv

On the size of $(K_t,\mathcal{T}_k)$ -co-critical graphs

Given an integer $r\ge1$ and graphs $G, H_1, \ldots, H_r$ , we write $G \rightarrow ({H}_1, \ldots, {H}_r)$ if every $r$ -coloring of the edges of $G$ contains a monochromatic copy of $H_i$ in color $i$ for some $i\in\{1, \ldots, r\}$ . A non-complete graph $G$ is $(H_1, \ldots, H_r)$ -co-critical if $G \nrightarrow ({H}_1, \ldots, {H}_r)$ , but $G+e\rightarrow ({H}_1, \ldots, {H}_r)$ for every edge $e$ in $\overline{G}$ . In this paper, motivated by Hanson and Toft's conjecture [Edge-colored saturated graphs, J Graph Theory 11(1987), 191--196], we study the minimum number of edges over all $(K_t, \mathcal{T}_k)$ -co-critical graphs on $n$ vertices, where $\mathcal{T}_k$ denotes the family of all trees on $k$ vertices. Following Day [Saturated graphs of prescribed minimum degree, Combin. Probab. Comput. 26 (2017), 201--207], we apply graph bootstrap percolation on a not necessarily $K_t$ -saturated graph to prove that for all $t\ge4$ and $k\ge \max\{6, t\}$ , there exists a constant $c(t, k)$ such that, for all $n \ge (t-1)(k-1)+1$ , if $G$ is a $(K_t, \mathcal{T}_k)$ -co-critical graph on $n$ vertices, then $e(G)\ge \left(\frac{4t-9}{2}+\frac{1}{2}\left\lceil \frac{k}{2} \right\rceil\right)n-c(t, k).$ Furthermore, this linear bound is asymptotically best possible when $t\in\{4,5\}$ and $k\ge6$ . The method we develop in this paper may shed some light on attacking Hanson and Toft's conjecture.

preprint2017arXiv

Star 5-edge-colorings of subcubic multigraphs

The star chromatic index of a multigraph $G$ , denoted $χ'_{s}(G)$ , is the minimum number of colors needed to properly color the edges of $G$ such that no path or cycle of length four is bi-colored. A multigraph $G$ is star $k$ -edge-colorable if $χ'_{s}(G)\le k$ . Dvořák, Mohar and Šámal [Star chromatic index, J Graph Theory 72 (2013), 313--326] proved that every subcubic multigraph is star $7$ -edge-colorable, and conjectured that every subcubic multigraph should be star $6$ -edge-colorable. Kerdjoudj, Kostochka and Raspaud considered the list version of this problem for simple graphs and proved that every subcubic graph with maximum average degree less than $7/3$ is star list- $5$ -edge-colorable. It is known that a graph with maximum average degree $14/5$ is not necessarily star $5$ -edge-colorable. In this paper, we prove that every subcubic multigraph with maximum average degree less than $12/5$ is star $5$ -edge-colorable.

preprint2016arXiv

Coloring Graphs with Forbidden Minors

Hadwiger's conjecture from 1943 states that for every integer $t\ge1$ , every graph either can be $t$ -colored or has a subgraph that can be contracted to the complete graph on $t+1$ vertices. As pointed out by Paul Seymour in his recent survey on Hadwiger's conjecture, proving that graphs with no $K_7$ minor are $6$ -colorable is the first case of Hadwiger's conjecture that is still open. It is not known yet whether graphs with no $K_7$ minor are $7$ -colorable. Using a Kempe-chain argument along with the fact that an induced path on three vertices is dominating in a graph with independence number two, we first give a very short and computer-free proof of a recent result of Albar and Gonçalves and generalize it to the next step by showing that every graph with no $K_t$ minor is $(2t-6)$ -colorable, where $t\in\{7,8,9\}$ . We then prove that graphs with no $K_8^-$ minor are $9$ -colorable and graphs with no $K_8^=$ minor are $8$ -colorable. Finally we prove that if Mader's bound for the extremal function for $K_p$ minors is true, then every graph with no $K_p$ minor is $(2t-6)$ -colorable for all $p\ge5$ . This implies our first result. We believe that the Kempe-chain method we have developed in this paper is of independent interest.

preprint2015arXiv

A Note on Weighted Rooted Trees

Let $T$ be a tree rooted at $r$ . Two vertices of $T$ are related if one is a descendant of the other; otherwise, they are unrelated. Two subsets $A$ and $B$ of $V(T)$ are unrelated if, for any $a\in A$ and $b\in B$ , $a$ and $b$ are unrelated. Let $ω$ be a nonnegative weight function defined on $V(T)$ with $\sum_{v\in V(T)}ω(v)=1$ . In this note, we prove that either there is an $(r, u)$ -path $P$ with $\sum_{v\in V(P)}ω(v)\ge \frac13$ for some $u\in V(T)$ , or there exist unrelated sets $A, B\subseteq V(T)$ such that $\sum_{a\in A }ω(a)\ge \frac13$ and $\sum_{b\in B }ω(b)\ge \frac13$ . The bound $\frac13$ is tight. This answers a question posed in a very recent paper of Bonamy, Bousquet and Thomassé.

Zi-Xia Song

Research overview

Is this your work?

10 publications

Every graph with no $\mathcal{K}_8^{-4}$ minor is $7$ -colorable

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

Properties of $8$ -contraction-critical graphs with no $K_7$ minor

Breaking the degeneracy barrier for coloring graphs with no $K_t$ minor

Gallai-Ramsey number of even cycles with chords

Gallai-Ramsey number of odd cycles with chords

On the size of $(K_t,\mathcal{T}_k)$ -co-critical graphs

Star 5-edge-colorings of subcubic multigraphs

Coloring Graphs with Forbidden Minors

A Note on Weighted Rooted Trees

See the researcher in context

Building this map preview

Zi-Xia Song

Research overview

Is this your work?

10 publications

Every graph with no K8−4\mathcal{K}_8^{-4}K8−4​ minor is 777-colorable

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

Properties of 888-contraction-critical graphs with no K7K_7K7​ minor

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

Gallai-Ramsey number of even cycles with chords

Gallai-Ramsey number of odd cycles with chords

On the size of (Kt,Tk)(K_t,\mathcal{T}_k)(Kt​,Tk​)-co-critical graphs

Star 5-edge-colorings of subcubic multigraphs

Coloring Graphs with Forbidden Minors

A Note on Weighted Rooted Trees

See the researcher in context

Building this map preview

Every graph with no $\mathcal{K}_8^{-4}$ minor is $7$ -colorable

Properties of $8$ -contraction-critical graphs with no $K_7$ minor

Breaking the degeneracy barrier for coloring graphs with no $K_t$ minor

On the size of $(K_t,\mathcal{T}_k)$ -co-critical graphs