Search for: All records

ABSTRACT We prove that for any graph , the total chromatic number of is at most . This saves one color in comparison with the result of Hind from 1992. In particular, our result says that if , then has a total coloring using at most colors. When is regular and has a sufficient number of vertices, we can actually save an additional two colors. Specifically, we prove that for any , there exists such that: if is an ‐regular graph on vertices with , then . This confirms the Total Coloring Conjecture for such graphs . 

ABSTRACT In 1956, Tutte proved the celebrated theorem that every 4‐connected planar graph is Hamiltonian. This result implies that every more than ‐tough planar graph on at least three vertices is Hamiltonian and so has a 2‐factor. Owens in 1999 constructed non‐Hamiltonian maximal planar graphs of toughness arbitrarily close to and asked whether there exists a maximal non‐Hamiltonian planar graph of toughness exactly . In fact, the graphs Owens constructed do not even contain a 2‐factor. Thus the toughness of exactly is the only case left in asking the existence of 2‐factors in tough planar graphs. This question was also asked by Bauer, Broersma, and Schmeichel in a survey. In this paper, we close this gap by constructing a maximal ‐tough plane graph with no 2‐factor, answering the question asked by Owens as well as by Bauer, Broersma, and Schmeichel. 

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. 

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. 

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. 

Abstract A spanning tree of a graph with no vertex of degree 2 is called a homeomorphically irreducible spanning tree (HIST) of the graph. In 1990, Albertson, Berman, Hutchinson, and Thomassen conjectured that every twin‐free graph with diameter 2 contains a HIST. Recently, Ando disproved this conjecture and characterized twin‐free graphs with diameter 2 that do contain a HIST. In this paper, we give a complete characterization of all graphs of diameter 2 that contain a HIST. This characterization gives alternative proofs for several known results. 

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. 

Let $$G$$ be a multigraph. A subset $$F$$ of $E(G)$ is an edge cover of $$G$$ if every vertex of $$G$$ is incident to an edge of $$F$$. The cover index, $$\xi(G)$$, is the largest number of edge covers into which the edges of $$G$$ can be partitioned. Clearly $$\xi(G) \le \delta(G)$$, the minimum degree of $$G$$. For $$U\subseteq V(G)$$, denote by $E^+(U)$ the set of edges incident to a vertex of $$U$$. When $|U|$ is odd, to cover all the vertices of $$U$$, any edge cover needs to contain at least $(|U|+1)/2$ edges from $E^+(U)$, indicating $$ \xi(G) \le |E^+(U)|/ ((|U|+1)/2)$$. Let $$\rho_c(G)$$, the co-density of $$G$$, be defined as the minimum of $|E^+(U)|/((|U|+1)/2)$ ranging over all $$U\subseteq V(G)$$, where $$|U| \ge 3$$ and $|U|$ is odd. Then $$\rho_c(G)$$ provides another upper bound on $$\xi(G)$$. Thus $$\xi(G) \le \min\{\delta(G), \lfloor \rho_c(G) \rfloor \}$$. For a lower bound on $$\xi(G)$$, in 1978, Gupta conjectured that $$\xi(G) \ge \min\{\delta(G)-1, \lfloor \rho_c(G) \rfloor \}$$. Gupta himself verified the conjecture for simple graphs, and Cao et al. recently verified this conjecture when $$\rho_c(G)$$ is not an integer. In this paper, we confirm the conjecture when the maximum multiplicity of $$G$$ is at most two or $$ \min\{\delta(G)-1, \lfloor \rho_c(G) \rfloor \} \le 6$$. The proof relies on a newly established result on edge colorings. The result holds independent interest and has the potential to significantly contribute towards resolving the conjecture entirely.