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
Ring graphs and Goldberg's bound on chromatic index
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
- PAR ID:
- 10110661
- Publisher / Repository:
- Wiley Blackwell (John Wiley & Sons)
- Date Published:
- Journal Name:
- Journal of Graph Theory
- Volume:
- 93
- Issue:
- 3
- ISSN:
- 0364-9024
- Page Range / eLocation ID:
- p. 440-449
- 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 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 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
-
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 non-bipartite, 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 non-bipartite 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
