An official website of the United States government
Abstract 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.
more »
« less
This content will become publicly available on June 1, 2026
On the Multigraph Overfull Conjecture
ABSTRACT A subgraph of a multigraph is overfull if Analogous to the Overfull Conjecture proposed by Chetwynd and Hilton in 1986, Stiebitz et al. formed the multigraph version of the conjecture as follows: Let be a multigraph with maximum multiplicity and maximum degree . Then has chromatic index if and only if contains no overfull subgraph. In this paper, we prove the following three results toward the Multigraph Overfull Conjecture for sufficiently large and even , where . (1) If is ‐regular with , then has a 1‐factorization. This result also settles a conjecture of the first author and Tipnis from 2001 up to a constant error in the lower bound of . (2) If contains an overfull subgraph and , then , where is the fractional chromatic index of . (3) If the minimum degree of is at least for any and contains no overfull subgraph, then . The proof is based on the decomposition of multigraphs into simple graphs and we prove a slightly weaker version of a conjecture due to the first author and Tipnis from 1991 on decomposing a multigraph into constrained simple graphs. The result is also of independent interest.
more »
« less
- Award ID(s):
- 2345869
- PAR ID:
- 10648720
- Publisher / Repository:
- Wiley
- Date Published:
- Journal Name:
- Journal of Graph Theory
- Volume:
- 109
- Issue:
- 2
- ISSN:
- 0364-9024
- Page Range / eLocation ID:
- 226 to 236
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
ABSTRACT A subgraph of a graph with maximum degree is ‐overfullif . Clearly, if contains a ‐overfull subgraph, then its chromatic index is . However, the converse is not true, as demonstrated by the Petersen graph. Nevertheless, three families of graphs are conjectured to satisfy the converse statement: (1) graphs with (the Overfull Conjecture of Chetwynd and Hilton), (2) planar graphs (Seymour's Exact Conjecture), and (3) graphs whose subgraph induced on the set of maximum degree vertices is the union of vertex‐disjoint cycles (the Core Conjecture of Hilton and Zhao). Over the past decades, these conjectures have been central to the study of edge coloring in simple graphs. Progress had been slow until recently, when the Core Conjecture was confirmed by the authors in 2024. This breakthrough was achieved by extending Vizing's classical fan technique to two larger families of trees: the pseudo‐multifan and the lollipop. This paper investigates the properties of these two structures, forming part of the theoretical foundation used to prove the Core Conjecture. We anticipate that these developments will provide insights into verifying the Overfull Conjecture for graphs where the subgraph induced by maximum‐degree vertices has relatively small maximum degree.more » « less
-
Abstract 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
-
Abstract Let be a simple graph. Let and be the maximum degree and the chromatic index of , respectively. We calloverfullif , andcriticalif for every proper subgraph of . Clearly, if is overfull then . Thecoreof , 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.more » « less
-
The Gyárfás–Sumner conjecture says that for every tree T and every integer t ≥ 1, if G is a graph with no clique of size t and with sufficiently large chromatic number, then G contains an induced subgraph isomorphic to T. This remains open, but we prove that under the same hypotheses, G contains a subgraph H isomorphic to T that is “path-induced”; that is, for some distinguished vertex r, every path of H with one end r is an induced path of G.more » « less
