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 May 9, 2026
Pseudo‐Multifan and Lollipop
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
- PAR ID:
- 10639888
- Publisher / Repository:
- Wiley
- Date Published:
- Journal Name:
- Journal of Graph Theory
- Volume:
- 110
- Issue:
- 2
- ISSN:
- 0364-9024
- Page Range / eLocation ID:
- 155 to 166
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
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 If is a list assignment of colors to each vertex of an ‐vertex graph , then anequitable‐coloringof is a proper coloring of vertices of from their lists such that no color is used more than times. A graph isequitably‐choosableif it has an equitable ‐coloring for every ‐list assignment . In 2003, Kostochka, Pelsmajer, and West (KPW) conjectured that an analog of the famous Hajnal–Szemerédi Theorem on equitable coloring holds for equitable list coloring, namely, that for each positive integer every graph with maximum degree at most is equitably ‐choosable. The main result of this paper is that for each and each planar graph , a stronger statement holds: if the maximum degree of is at most , then is equitably ‐choosable. In fact, we prove the result for a broader class of graphs—the class of the graphs in which each bipartite subgraph with has at most edges. Together with some known results, this implies that the KPW Conjecture holds for all graphs in , in particular, for all planar graphs. We also introduce the new stronger notion ofstrongly equitable(SE, for short) list coloring and prove all bounds for this parameter. An advantage of this is that if a graph is SE ‐choosable, then it is both equitably ‐choosable and equitably ‐colorable, while neither of being equitably ‐choosable and equitably ‐colorable implies the other.more » « less
-
We give a combinatorial polynomial-time algorithm to find a maximum weight independent set in perfect graphs of bounded degree that do not contain a prism or a hole of length four as an induced subgraph. An even pair in a graph is a pair of vertices all induced paths between which are even. An even set is a set of vertices every two of which are an even pair. We show that every perfect graph that does not contain a prism or a hole of length four as an induced subgraph has a balanced separator which is the union of a bounded number of even sets, where the bound depends only on the maximum degree of the graph. This allows us to solve the maximum weight independent set problem using the well-known submodular function minimization algorithm. Funding: This work was supported by the Engineering and Physical Sciences Research Council [Grant EP/V002813/1]; the National Science Foundation [Grants DMS-1763817, DMS-2120644, and DMS-2303251]; and Alexander von Humboldt-Stiftung.more » « less
-
Abstract We suggest two related conjectures dealing with the existence of spanning irregular subgraphs of graphs. The first asserts that any $$d$$ -regular graph on $$n$$ vertices contains a spanning subgraph in which the number of vertices of each degree between $$0$$ and $$d$$ deviates from $$\frac{n}{d+1}$$ by at most $$2$$ . The second is that every graph on $$n$$ vertices with minimum degree $$\delta$$ contains a spanning subgraph in which the number of vertices of each degree does not exceed $$\frac{n}{\delta +1}+2$$ . Both conjectures remain open, but we prove several asymptotic relaxations for graphs with a large number of vertices $$n$$ . In particular we show that if $$d^3 \log n \leq o(n)$$ then every $$d$$ -regular graph with $$n$$ vertices contains a spanning subgraph in which the number of vertices of each degree between $$0$$ and $$d$$ is $$(1+o(1))\frac{n}{d+1}$$ . We also prove that any graph with $$n$$ vertices and minimum degree $$\delta$$ contains a spanning subgraph in which no degree is repeated more than $$(1+o(1))\frac{n}{\delta +1}+2$$ times.more » « less
