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
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 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
-
Abstract Motivated by the study of greedy algorithms for graph coloring, we introduce a new graph parameter, which we callweak degeneracy. By definition, every ‐degenerate graph is also weakly ‐degenerate. On the other hand, if is weakly ‐degenerate, then (and, moreover, the same bound holds for the list‐chromatic and even the DP‐chromatic number of ). It turns out that several upper bounds in graph coloring theory can be phrased in terms of weak degeneracy. For example, we show that planar graphs are weakly 4‐degenerate, which implies Thomassen's famous theorem that planar graphs are 5‐list‐colorable. We also prove a version of Brooks's theorem for weak degeneracy: a connected graph of maximum degree is weakly ‐degenerate unless . (By contrast, all ‐regular graphs have degeneracy .) We actually prove an even stronger result, namely that for every , there is such that if is a graph of weak degeneracy at least , then either contains a ‐clique or the maximum average degree of is at least . Finally, we show that graphs of maximum degree and either of girth at least 5 or of bounded chromatic number are weakly ‐degenerate, which is best possible up to the value of the implied constant.more » « less
-
Abstract Alinear forestis a disjoint union of path graphs. Thelinear arboricity of a graph, denoted by , is the least number of linear forests into which the graph can be partitioned. Clearly, for any graph of maximum degree . For the upper bound, the long‐standingLinear Arboricity Conjecture(LAC) due to Akiyama, Exoo, and Harary from 1981 asserts that . A graph is apseudoforestif each of its components contains at most one cycle. In this paper, we prove thatthe union of any two pseudoforests of maximum degree up to 3 can be decomposed into three linear forests. Combining it with a recent result of Wdowinski on the minimum number of pseudoforests into which a graph can be decomposed, we prove that the LAC holds for the following simple graph classes: ‐degenerate graphs with maximum degree , all graphs on nonnegative Euler characteristic surfaces provided the maximum degree , and graphs on negative Euler characteristic surfaces provided the maximum degree , as well as graphs with no ‐minor satisfying some conditions on maximum degrees.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript
- Journal Article:
- https://doi.org/10.1002/jgt.23221
