Let be a simple graph with maximum degree . A subgraph of is overfull if . Chetwynd and Hilton in 1986 conjectured that a graph with has chromatic index if and only if contains no overfull subgraph. Let , be sufficiently large, and be graph on vertices with minimum degree at least . It was shown that the conjecture holds for if is even. In this paper, the same result is proved if is odd. As far as we know, this is the first result on the Overfull Conjecture for graphs of odd order and with a minimum degree constraint.
Let be a multigraph with maximum degree and chromatic index . If is bipartite then . Otherwise, by a theorem of Goldberg, , where denotes the odd girth of . Stiebitz, Scheide, Toft, and Favrholdt in their book conjectured that if then contains as a subgraph a ring graph with the same chromatic index. Vizing's characterization of graphs with chromatic index attaining the Shannon's bound showed the above conjecture holds for . Stiebitz et al verified the conjecture for graphs with and . McDonald proved the conjecture when is divisible by . In this paper, we show that the chromatic index condition alone is not sufficient to give the conclusion in the conjecture. On the positive side, we show that the conjecture holds for every with , and the maximum degree condition is best possible. This positive result leans on the positive resolution of the Goldberg‐Seymour conjecture.
more » « less NSFPAR ID:
 10110661
 Publisher / Repository:
 Wiley Blackwell (John Wiley & Sons)
 Date Published:
 Journal Name:
 Journal of Graph Theory
 Volume:
 93
 Issue:
 3
 ISSN:
 03649024
 Page Range / eLocation ID:
 p. 440449
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Abstract 
Abstract Let be a simple graph. Let and be the maximum degree and the chromatic index of , respectively. We call
overfull if , andcritical if for every proper subgraph of . Clearly, if is overfull then . Thecore of , denoted by , is the subgraph of induced by all its maximum degree vertices. We believe that utilizing the core degree condition could be considered as an approach to attack the overfull conjecture. Along this direction, we in this paper show that for any integer , if is critical with and , then is overfull. 
null (Ed.)Abstract In this paper, we prove a tight minimum degree condition in general graphs for the existence of paths between two given endpoints whose lengths form a long arithmetic progression with common difference one or two. This allows us to obtain a number of exact and optimal results on cycle lengths in graphs of given minimum degree, connectivity or chromatic number. More precisely, we prove the following statements by a unified approach: 1. Every graph $G$ with minimum degree at least $k+1$ contains cycles of all even lengths modulo $k$; in addition, if $G$ is $2$connected and nonbipartite, then it contains cycles of all lengths modulo $k$. 2. For all $k\geq 3$, every $k$connected graph contains a cycle of length zero modulo $k$. 3. Every $3$connected nonbipartite graph with minimum degree at least $k+1$ contains $k$ cycles of consecutive lengths. 4. Every graph with chromatic number at least $k+2$ contains $k$ cycles of consecutive lengths. The 1st statement is a conjecture of Thomassen, the 2nd is a conjecture of Dean, the 3rd is a tight answer to a question of Bondy and Vince, and the 4th is a conjecture of Sudakov and Verstraëte. All of the above results are best possible.more » « less

Abstract A
linear forest is a union of vertex‐disjoint paths, and thelinear arboricity of a graph , denoted by , is the minimum number of linear forests into which the edge set of can be partitioned. Clearly, for a graph with maximum degree . On the other hand, theLinear Arboricity Conjecture due to Akiyama, Exoo, and Harary from 1981 asserts that for every graph . This conjecture has been verified for planar graphs and graphs whose maximum degree is at most , or is equal to or . Given a positive integer , a graph is ‐degenerate if it can be reduced to a trivial graph by successive removal of vertices with a degree at most . We prove that for any ‐degenerate graph provided . 
Abstract A graph is ‐
free if it has no induced subgraph isomorphic to , and G  denotes the number of vertices of . A conjecture of Conlon, Sudakov and the second author asserts that:For every graph , there exists such that in every ‐free graph with 
This is equivalent to:G  there are two disjoint sets of vertices, of sizes at least and , complete or anticomplete to each other.The “sparse linear conjecture”: For every graph , there exists such that in every ‐free graph with , either some vertex has degree at least , or there are two disjoint sets of vertices, of sizes at least and , anticomplete to each other.
The sparse linear conjecture holds for all almost‐bipartite graphs .
For every almost‐bipartite graph , there exist such that for every graph with and maximum degree less than , and for every with , either contains induced copies of , or there are two disjoint sets with and , and with at most edges between them.
For every graph , there exists such that in every ‐free graph with vertices, either some vertex has degree at least , or there are two disjoint sets of vertices with , anticomplete to each other.