Source author record

Wenan Zang

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

3works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Proof of the Goldberg-Seymour Conjecture on Edge-Colorings of Multigraphs

Given a multigraph $G=(V,E)$ , the {\em edge-coloring problem} (ECP) is to color the edges of $G$ with the minimum number of colors so that no two adjacent edges have the same color. This problem can be naturally formulated as an integer program, and its linear programming relaxation is called the {\em fractional edge-coloring problem} (FECP). In the literature, the optimal value of ECP (resp. FECP) is called the {\em chromatic index} (resp. {\em fractional chromatic index}) of $G$ , denoted by $χ'(G)$ (resp. $χ^*(G)$ ). Let $Δ(G)$ be the maximum degree of $G$ and let $Γ(G)=\max \Big\{\frac{2|E(U)|}{|U|-1}:\,\, U \subseteq V, \,\, |U|\ge 3 \hskip 2mm {\rm and \hskip 2mm odd} \Big\},$ where $E(U)$ is the set of all edges of $G$ with both ends in $U$ . Clearly, $\max\{Δ(G), \, \lceil Γ(G) \rceil \}$ is a lower bound for $χ'(G)$ . As shown by Seymour, $χ^*(G)=\max\{Δ(G), \, Γ(G)\}$ . In the 1970s Goldberg and Seymour independently conjectured that $χ'(G) \le \max\{Δ(G)+1, \, \lceil Γ(G) \rceil\}$ . Over the past four decades this conjecture, a cornerstone in modern edge-coloring, has been a subject of extensive research, and has stimulated a significant body of work. In this paper we present a proof of this conjecture. Our result implies that, first, there are only two possible values for $χ'(G)$ , so an analogue to Vizing's theorem on edge-colorings of simple graphs, a fundamental result in graph theory, holds for multigraphs; second, although it is $NP$ -hard in general to determine $χ'(G)$ , we can approximate it within one of its true value, and find it exactly in polynomial time when $Γ(G)>Δ(G)$ ; third, every multigraph $G$ satisfies $χ'(G)-χ^*(G) \le 1$ , so FECP has a fascinating integer rounding property.

preprint2016arXiv

On Box-Perfect Graphs

Let $G=(V,E)$ be a graph and let $A_G$ be the clique-vertex incidence matrix of $G$ . It is well known that $G$ is perfect iff the system $A_{_G}\mathbf x\le \mathbf 1$ , $\mathbf x\ge\mathbf0$ is totally dual integral (TDI). In 1982, Cameron and Edmonds proposed to call $G$ box-perfect if the system $A_{_G}\mathbf x\le \mathbf 1$ , $\mathbf x\ge\mathbf0$ is box-totally dual integral (box-TDI), and posed the problem of characterizing such graphs. In this paper we prove the Cameron-Edmonds conjecture on box-perfectness of parity graphs, and identify several other classes of box-perfect graphs. We also develop a general and powerful method for establishing box-perfectness.

preprint2014arXiv

Coloring Digraphs with Forbidden Cycles

Let $k$ and $r$ be two integers with $k \ge 2$ and $k\ge r \ge 1$ . In this paper we show that (1) if a strongly connected digraph $D$ contains no directed cycle of length $1$ modulo $k$ , then $D$ is $k$ -colorable; and (2) if a digraph $D$ contains no directed cycle of length $r$ modulo $k$ , then $D$ can be vertex-colored with $k$ colors so that each color class induces an acyclic subdigraph in $D$ . The first result gives an affirmative answer to a question posed by Tuza in 1992, and the second implies the following strong form of a conjecture of Diwan, Kenkre and Vishwanathan: If an undirected graph $G$ contains no cycle of length $r$ modulo $k$ , then $G$ is $k$ -colorable if $r\ne 2$ and $(k+1)$ -colorable otherwise. Our results also strengthen several classical theorems on graph coloring proved by Bondy, Erdős and Hajnal, Gallai and Roy, Gyárfás, etc.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.