Given a simple graph $G$, denote by $\Delta(G)$, $\delta(G)$, and $\chi'(G)$ the maximum degree, the minimum degree, and the chromatic index of $G$, respectively. We say $G$ is $\Delta$-critical if $\chi'(G)=\Delta(G)+1$ and $\chi'(H)\le \Delta(G)$ for every proper subgraph $H$ of $G$, and $G$ is overfull if $|E(G)|>\Delta(G) \lfloor |V(G)|/2 \rfloor$. Since a maximum matching in $G$ can have size at most $\lfloor |V(G)|/2 \rfloor$, it follows that $\chi'(G) = \Delta(G) +1$ if $G$ is overfull. Conversely, let $G$ be a $\Delta$-critical graph. The well known overfull conjecture of Chetwynd and Hilton asserts that $G$ is overfull provided $\Delta(G) > |V(G)|/3$. In this paper, we show that any $\Delta$-critical graph $G$ is overfull if $\Delta(G) - 7\delta(G)/4\ge (3|V(G)|-17)/4$.

Let $G$ be an $n$-vertex graph with $n\ge 3$. A classic result of Dirac from 1952 asserts that $G$ is hamiltonian if $\delta(G)\ge n/2$. Dirac's theorem is one of the most influential results in the study of hamiltonicity and by now there are many related known results(see, e.g., [J. A. Bondy, Handbook of Combinatorics, Vol. 1, MIT Press, Cambridge, MA, 1995, pp. 3--110]. A Halin graph is a planar graph consisting of two edge-disjoint subgraphs: a spanning tree of at least four vertices and with no vertex of degree 2, and a cycle induced by the set of the leaves of the spanning tree. Halin graphs possess rich hamiltonicity properties such as being hamiltonian, hamiltonian connected, and almost pancyclic. As a continuous “generalization” of Dirac's theorem, in this paper, we show that there exists a positive integer $n_0$ such that any graph $G$ with $n\ge n_0$ vertices and $\delta(G)\ge (n+1)/2$ contains a spanning and pancyclic Halin subgraph $H$. In addition, for every nonhamiltonian cycle $C$ in $H$, there is a cycle $C'$ longer than $C$ such that $C'$ contains all vertices from $C$ and at most two more vertices not from $C$.

Bollobás and Thomason showed that a multigraph of order $n$ and size at least $n+c\,(c\ge 1)$ contains a cycle of length at most $2(\lfloor n/c\rfloor+1)\lfloor \log_2 2c\rfloor$. We show in this paper that a multigraph (with no loop) of order $n$ and minimum degree at least 5 contains a chorded cycle (a cycle with a chord) of length at most $300\log_2 n$. As an application of this result, we show that a graph of sufficiently large order with minimum degree at least $3k+8$ contains $k$ vertex-disjoint chorded cycles of the same length, which is analogous to Verstraëte's result: A graph of sufficiently large order with minimum degree at least $2k$ contains $k$ vertex-disjoint cycles of the same length.

The well-known Chvátal--Erdös theorem states that every graph $G$ of order at least three with $\alpha(G)\le\kappa(G)$ has a Hamiltonian cycle, where $\alpha(G)$ and $\kappa(G)$ are the independence number and the connectivity of $G$, respectively. Oberly and Sumner [J. Graph Theory, 3 (1979), pp. 351--356] have proved that every connected, locally connected claw-free graph of order at least three has a Hamiltonian cycle. We study the connection of these two theorems. For $x\in V(G)$, let $B(x)$ denote the subgraph of $G$ induced by the closed neighborhood of $x$. Then the theorem by Oberly and Sumner says that a connected graph $G$ of order at least three satisfying $\alpha(B(x))\le 2\le \kappa(B(x))$ for every vertex $x$ has a Hamiltonian cycle. The comparison of this theorem with the Chvátal--Erdös theorem leads us to suspect that the threshold 2 between $\alpha(B(x))$ and $\kappa(B(x))$ is not necessary. We say that $G$ satisfies the local Chvátal--Erdös condition if $\alpha(B(x))\le\kappa(B(x))$ holds for every vertex $x$ in $G$. The second author conjectured that if the order of a connected graph $G$ is at least three and satisfies the local Chvátal--Erdös condition, then $G$ has a Hamiltonian cycle. In this paper, we support this conjecture by proving that under this assumption, $G$ is $1$-tough and has a $2$-factor.