Edge proximity and matching extension in projective planar graphs

A graph $G$ with at least $2m+2$ vertices is said to be distance $d$ $m$-extendable if, for any matching $M$ of $G$ with $m$ edges in which the edges lie at distance at least $d$ pairwise, there exists a perfect matching of $G$ containing $M$. In this paper we prove that every 5-connected triangulation on the projective plane of even order is distance 3 7-extendable and distance 4 $m$-extendable for any $m$.     

Erratum: The average degree of an edge-chromatic critical graph II

In the article “The average degree of an edge-chromatic critical graph II” by Douglas R. Woodall (J. Graph Theory 56 (2007), 194-218), it was claimed that the average degree of an edge-chromatic critical graph with maximum degree $\mathrm{\Delta }$ is at least $\text{◂⋅▸}\frac{2}{3}\left(\mathrm{\Delta }+1\right)$ if $\mathrm{\Delta }⩾2$, at least $\text{◂+▸}\frac{2}{3}\mathrm{\Delta }+1$ if $\mathrm{\Delta }⩾8$, and at least $\text{◂⋅▸}\frac{2}{3}\left(\mathrm{\Delta }+2\right)$ if $\mathrm{\Delta }⩾15$. Unfortunately there were mistakes in the proof of the last two of these results, which are now proved only if $\mathrm{\Delta }⩾18$ and $\mathrm{\Delta }⩾30$, respectively.     

On the imaginary parts of chromatic roots

While much attention has been directed to the maximum modulus and maximum real part of chromatic roots of graphs of order $n$ (ie, with $n$ vertices), relatively little is known about the maximum imaginary part of such graphs. We prove that the maximum imaginary part can grow linearly in the order of the graph. We also show that for any fixed $\text{◂+▸}p\in \left(0,1\right)$, almost every random graph $G$ in the Erdös-Rényi model has a nonreal root.     

An Ore-type condition for large k-factor and disjoint perfect matchings

Win conjectured that a graph $G$ on $n$ vertices contains $k$ disjoint perfect matchings, if the degree sum of any two nonadjacent vertices is at least $n+k-2$, where $n$ is even and $n\ge k+2$. In this paper, we prove that Win's conjecture is true for $k\ge n∕2$, where $n$ is sufficiently large. To show this result, we prove a theorem on $k$-factor in a graph under some Ore-type condition. Our main tools include Tutte's $k$-factor theorem, the Karush-Kuhn-Tucker theorem on convex optimization and the solution to the long-standing 1-factor decomposition conjecture.     

Colorings versus list colorings of uniform hypergraphs

Let $r$ be an integer with $r\ge 2$ and $G$ be a connected $r$-uniform hypergraph with $m$ edges. By refining the broken cycle theorem for hypergraphs, we show that if $k>\text{◂/▸}\frac{m-1}{\ln (1+\sqrt{2})}\approx \text{◂⋅▸}1.135\left(m-1\right)$, then the $k$-list assignment of $G$ admitting the fewest colorings is the constant list assignment. This extends the previous results of Donner, Thomassen, and the current authors for graphs.