Source author record

Guangming Jing

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

5works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Overfullness of edge-critical graphs with small minimal core degree

Let $G$ be a simple graph. Denote by $n$ , $Δ(G)$ and $χ' (G)$ be the order, the maximum degree and the chromatic index of $G$ , respectively. We call $G$ \emph{overfull} if $|E(G)|/\lfloor n/2\rfloor > Δ(G)$ , and {\it critical} if $χ'(H) < χ'(G)$ for every proper subgraph $H$ of $G$ . Clearly, if $G$ is overfull then $χ'(G) = Δ(G)+1$ . The \emph{core} of $G$ , denoted by $G_Δ$ , is the subgraph of $G$ induced by all its maximum degree vertices. We believe that utilizing the core degree condition could be considered as an approach to attacking the overfull conjecture. Along this direction, we in this paper show that for any integer $k\geq 2$ , if $G$ is critical with $Δ(G)\geq \frac{2}{3}n+\frac{3k}{2}$ and $δ(G_Δ)\leq k$ , then $G$ is overfull.

preprint2022arXiv

Precoloring extension of Vizing's Theorem for multigraphs

Let $G$ be a graph with maximum degree $Δ(G)$ and maximum multiplicity $μ(G)$ . Vizing and Gupta, independently, proved in the 1960s that the chromatic index of $G$ is at most $Δ(G)+μ(G)$ . The distance between two edges $e$ and $f$ in $G$ is the length of a shortest path connecting an endvertex of $e$ and an endvertex of $f$ . A distance- $t$ matching is a set of edges having pairwise distance at least $t$ . Edwards et al. proposed the following conjecture: For any graph $G$ , using the palette $\{1, \dots, Δ(G)+μ(G)\}$ , any precoloring on a distance- $2$ matching can be extended to a proper edge coloring of $G$ . Girão and Kang verified this conjecture for distance- $9$ matchings. In this paper, we improve the required distance from $9$ to $3$ for multigraphs $G$ with $μ(G) \ge 2$ .

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.

preprint2020arXiv

Proof of the Core Conjecture of Hilton and Zhao

Let $G$ be a simple graph with maximum degree $Δ$ . We call $G$ \emph{overfull} if $|E(G)|>Δ\lfloor |V(G)|/2\rfloor$ . The \emph{core} of $G$ , denoted $G_Δ$ , is the subgraph of $G$ induced by its vertices of degree $Δ$ . A classic result of Vizing shows that $χ'(G)$ , the chromatic index of $G$ , is either $Δ$ or $Δ+1$ . It is NP-complete to determine the chromatic index for a general graph. However, if $G$ is overfull then $χ'(G)=Δ+1$ . Hilton and Zhao in 1996 conjectured that if $G$ is a simple connected graph with $Δ\ge 3$ and $Δ(G_Δ)\le 2$ , then $χ'(G)=Δ+1$ if and only if $G$ is overfull or $G=P^*$ , where $P^*$ is obtained from the Petersen graph by deleting a vertex. This conjecture, if true, implies an easy approach for calculating $χ'(G)$ for graphs $G$ satisfying the conditions. The progress on the conjecture has been slow: it was only confirmed for $Δ=3,4$ , respectively, in 2003 and 2017. In this paper, we confirm this conjecture for all $Δ\ge 4$ .

preprint2013arXiv

Sign patterns with minimum rank 3 and point-line configurations

A \emph{sign pattern (matrix)} is a matrix whose entries are from the set $\{+, -, 0\}$ . The \emph{minimum rank} (respectively, \emph{rational minimum rank}) of a sign pattern matrix $\cal A$ is the minimum of the ranks of the real (respectively, rational) matrices whose entries have signs equal to the corresponding entries of $\cal A$ . A sign pattern $\cal A$ is said to be \emph{condensed} if $\cal A$ has no zero row or column and no two rows or columns are identical or negatives of each other. In this paper, a new direct connection between condensed $m \times n$ sign patterns with minimum rank $r$ and $m$ point-- $n$ hyperplane configurations in ${\mathbb R}^{r-1}$ is established. In particular, condensed sign patterns with minimum rank 3 are closed related to point--line configurations on the plane. It is proved that for any sign pattern $\cal A$ with minimum rank $r\geq 3$ , if the number of zero entries on each column of $\cal A$ is at most $r-1$ , then the rational minimum rank of $\cal A$ is also $r$ . Furthermore, we construct the smallest known sign pattern whose minimum rank is 3 but whose rational minimum rank is greater than 3.

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.

Guangming Jing

Research overview

Is this your work?

5 publications

Overfullness of edge-critical graphs with small minimal core degree

Precoloring extension of Vizing's Theorem for multigraphs

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

Proof of the Core Conjecture of Hilton and Zhao

Sign patterns with minimum rank 3 and point-line configurations

See the researcher in context

Building this map preview