Search

A simple graph G with maximum degree Δ is overfull if | E (G) | > Δ ⌊ | V (G) | / 2 ⌋. The core of G , denoted G Δ , is the subgraph of G induced by its vertices of degree Δ. Clearly, the chromatic index of G equals Δ + 1 if G is overfull. Conversely, Hilton and Zhao in 1996 conjectured that if G is a simple connected graph with Δ ≥ 3 and Δ (G Δ) ≤ 2 , then χ ′ (G) = Δ + 1 implies that G is overfull or G = P ⁎ , where P ⁎ is obtained from the Petersen graph by deleting a vertex. Cariolaro and Cariolaro settled the base case Δ = 3 in 2003, and Cranston and Rabern proved the next case, Δ = 4 , in 2019. In this paper, we give a proof of this conjecture for all Δ ≥ 4. [ABSTRACT FROM AUTHOR]

Let G $G$ be a simple graph. Let Δ(G) ${\rm{\Delta }}(G)$ and χ′(G) $\chi ^{\prime} (G)$ be the maximum degree and the chromatic index of G $G$, respectively. We call G $G$overfull if ∣E(G)∣∕⌊∣V(G)∣∕2⌋>Δ(G) $| E(G)| \unicode{x02215}\lfloor | V(G)| \unicode{x02215}2\rfloor \gt {\rm{\Delta }}(G)$, and critical if χ′(H)<χ′(G) $\chi ^{\prime} (H)\lt \chi ^{\prime} (G)$ for every proper subgraph H $H$ of G $G$. Clearly, if G $G$ is overfull then χ′(G)=Δ(G)+1 $\chi ^{\prime} (G)={\rm{\Delta }}(G)+1$. The core of G $G$, denoted by GΔ ${G}_{{\rm{\Delta }}}$, is the subgraph of G $G$ 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 k≥2 $k\ge 2$, if G $G$ is critical with Δ(G)≥23n+3k2 ${\rm{\Delta }}(G)\ge \frac{2}{3}n+\frac{3k}{2}$ and δ(GΔ)≤k $\delta ({G}_{{\rm{\Delta }}})\le k$, then G $G$ is overfull. [ABSTRACT FROM AUTHOR]

The mean subtree order of a given graph G $G$, denoted μ(G) $\mu (G)$, is the average number of vertices in a subtree of G $G$. Let G $G$ be a connected graph. Chin et al. conjectured that if H $H$ is a proper spanning supergraph of G $G$, then μ(H)>μ(G) $\mu (H)\gt \mu (G)$. Cameron and Mol disproved this conjecture by showing that there are infinitely many pairs of graphs H $H$ and G $G$ with H⊃G $H\supset G$, V(H)=V(G) $V(H)=V(G)$ and |E(H)|=|E(G)|+1 $|E(H)|=|E(G)|+1$ such that μ(H)<μ(G) $\mu (H)\lt \mu (G)$. They also conjectured that for every positive integer k $k$, there exists a pair of graphs G $G$ and H $H$ with H⊃G $H\supset G$, V(H)=V(G) $V(H)=V(G)$, and |E(H)|=|E(G)|+k $|E(H)|=|E(G)|+k$ such that μ(H)<μ(G) $\mu (H)\lt \mu (G)$. Furthermore, they proposed that μ(Km+nK1)<μ(Km,n) $\mu ({K}_{m}+n{K}_{1})\lt \mu ({K}_{m,n})$ provided n≫m $n\gg m$. In this note, we confirm these two conjectures. [ABSTRACT FROM AUTHOR]

A linear forest is a disjoint union of path graphs. The linear arboricity of a graphG $G$, denoted by la(G) $\text{la}(G)$, is the least number of linear forests into which the graph can be partitioned. Clearly, la(G)≥⌈Δ(G)∕2⌉ $\text{la}(G)\ge \lceil {\rm{\Delta }}(G)\unicode{x02215}2\rceil $ for any graph of maximum degree Δ(G) ${\rm{\Delta }}(G)$. For the upper bound, the long‐standing Linear Arboricity Conjecture (LAC) due to Akiyama, Exoo, and Harary from 1981 asserts that la(G)≤⌈(Δ(G)+1)∕2⌉ $\text{la}(G)\le \lceil ({\rm{\Delta }}(G)+1)\unicode{x02215}2\rceil $. A graph is a pseudoforest if each of its components contains at most one cycle. In this paper, we prove that the 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: k $k$‐degenerate graphs with maximum degree Δ≥3k−1 ${\rm{\Delta }}\ge 3k-1$, all graphs on nonnegative Euler characteristic surfaces provided the maximum degree Δ≠7 ${\rm{\Delta }}\ne 7$, and graphs on negative Euler characteristic ϵ $\epsilon $ surfaces provided the maximum degree Δ≥35+49−24ϵ4−1 ${\rm{\Delta }}\ge 3\unicode{x02308}\frac{5+\sqrt{49-24\epsilon }}{4}\unicode{x02309}-1$, as well as graphs with no Kt ${K}_{t}$‐minor satisfying some conditions on maximum degrees. [ABSTRACT FROM AUTHOR]

A linear forest is a union of vertex‐disjoint paths, and the linear arboricity of a graph G $G$, denoted by la(G) $\,\text{la}(G)$, is the minimum number of linear forests into which the edge set of G $G$ can be partitioned. Clearly, la(G)≥⌈Δ(G)∕2⌉ $\,\text{la}(G)\ge \lceil {\rm{\Delta }}(G)\unicode{x02215}2\rceil $ for a graph G $G$ with maximum degree Δ(G) ${\rm{\Delta }}(G)$. On the other hand, the Linear Arboricity Conjecture due to Akiyama, Exoo, and Harary from 1981 asserts that la(G)≤⌈(Δ(G)+1)∕2⌉ $\,\text{la}(G)\le \lceil ({\rm{\Delta }}(G)+1)\unicode{x02215}2\rceil $ for every graph G $G$. This conjecture has been verified for planar graphs and graphs whose maximum degree is at most 6 $6$, or is equal to 8 $8$ or 10 $10$. Given a positive integer k $k$, a graph G $G$ is k $k$‐degenerate if it can be reduced to a trivial graph by successive removal of vertices with a degree at most k $k$. We prove that for any k $k$‐degenerate graph G,la(G)=⌈Δ(G)∕2⌉ $G,\,\text{la}(G)=\lceil {\rm{\Delta }}(G)\unicode{x02215}2\rceil $ provided Δ(G)≥2k2−k ${\rm{\Delta }}(G)\ge 2{k}^{2}-k$. [ABSTRACT FROM AUTHOR]

The chromatic index χ ′ (G) of a graph G is the least number of colors assigned to the edges of G such that no two adjacent edges receive the same color. The total chromatic number χ ″ (G) of a graph G is the least number of colors assigned to the edges and vertices of G such that no two adjacent edges receive the same color, no two adjacent vertices receive the same color and no edge has the same color as its two endpoints. The chromatic index and the total chromatic number are two of few fundamental graph parameters, and their correlation has always been a subject of intensive study in graph theory. By definition, χ ′ (G) ≤ χ ″ (G) for every graph G. In 1984, Goldberg conjectured that for any multigraph G , if χ ′ (G) ≥ Δ (G) + 3 then χ ″ (G) = χ ′ (G). In this paper, we show that Goldberg's conjecture is asymptotically true. More specifically, we prove that for a multigraph G with maximum degree Δ sufficiently large, χ ″ (G) = χ ′ (G) provided χ ′ (G) ≥ Δ + 10 Δ 35 / 36. When χ ′ (G) ≥ Δ (G) + 2 , the chromatic index χ ′ (G) is completely determined by the fractional chromatic index. Consequently, the total chromatic number χ ″ (G) can be computed in polynomial-time in this case. [ABSTRACT FROM AUTHOR]

Let G $G$ be a simple graph with maximum degree Δ(G) ${\rm{\Delta }}(G)$ and chromatic index χ′(G) $\chi ^{\prime} (G)$. A classical result of Vizing shows that either χ′(G)=Δ(G) $\chi ^{\prime} (G)={\rm{\Delta }}(G)$ or χ′(G)=Δ(G)+1 $\chi ^{\prime} (G)={\rm{\Delta }}(G)+1$. A simple graph G $G$ is called edge‐Δ ${\rm{\Delta }}$‐critical if G $G$ is connected, χ′(G)=Δ(G)+1 $\chi ^{\prime} (G)={\rm{\Delta }}(G)+1$ and χ′(G−e)=Δ(G) $\chi ^{\prime} (G-e)={\rm{\Delta }}(G)$ for every e∈E(G) $e\in E(G)$. Let G $G$ be an n $n$‐vertex edge‐Δ ${\rm{\Delta }}$‐critical graph. Vizing conjectured that α(G) $\alpha (G)$, the independence number of G $G$, is at most n2 $\frac{n}{2}$. The current best result on this conjecture, shown by Woodall, is α(G)<3n5 $\alpha (G)\lt \frac{3n}{5}$. We show that for any given ε∈(0,1) $\varepsilon \in (0,1)$, there exist positive constants d0(ε) ${d}_{0}(\varepsilon)$ and D0(ε) ${D}_{0}(\varepsilon)$ such that if G $G$ is an n $n$‐vertex edge‐Δ ${\rm{\Delta }}$‐critical graph with minimum degree at least d0 ${d}_{0}$ and maximum degree at least D0 ${D}_{0}$, then α(G)<12+εn $\alpha (G)\lt \left(\frac{1}{2}+\varepsilon \right)n$. In particular, we show that if G $G$ is an n $n$‐vertex edge‐Δ ${\rm{\Delta }}$‐critical graph with minimum degree at least d $d$ and Δ(G)≥(d+1)4.5d+11.5 ${\rm{\Delta }}(G)\ge {(d+1)}^{4.5d+11.5}$, then α(G)<7n12ifd=3,4n7ifd=4,d+2+(d−1)d32d+4+(d−1)d3n<4n7ifd≥19. $\alpha (G)\lt \left.\left\{\displaystyle \begin{array}{cc}\frac{7n}{12} & \,\text{if}\,\,d=3,\\ \frac{4n}{7} & \,\text{if}\,\,d=4,\\ \frac{d+2+\sqrt[3]{(d-1)d}}{2d+4+\sqrt[3]{(d-1)d}}n\lt \frac{4n}{7} & \,\text{if}\,\,d\ge 19.\end{array}\right.$ [ABSTRACT FROM AUTHOR]

Let G be a simple graph, and let n , Δ (G) and χ ′ (G) be the order, the maximum degree and the chromatic index of G , respectively. We call G overfull if | E (G) | / ⌊ n / 2 ⌋ > Δ (G) , and critical if χ ′ (H) < χ ′ (G) for every proper subgraph H of G. Clearly, if G is overfull then χ ′ (G) = Δ (G) + 1 by Vizing's Theorem. The core of G , denoted by G Δ , is the subgraph of G induced by all its maximum degree vertices. Hilton and Zhao conjectured that for any critical class 2 graph G with Δ (G) ≥ 4 , if the maximum degree of G Δ is at most two, then G is overfull, which in turn gives Δ (G) > n / 2 + 1. We show that for any critical class 2 graph G , if the minimum degree of G Δ is at most two and Δ (G) > n / 2 + 1 , then G is overfull. [ABSTRACT FROM AUTHOR]

We call a graph G $G$ a k $k$‐threshold graph if there are k $k$ distinct real numbers θ1,θ2,...,θk ${\theta }_{1},{\theta }_{2},\ldots ,{\theta }_{k}$ and a mapping r:V(G)→R $r:V(G)\to {\mathbb{R}}$ such that for any two vertices u,v∈V(G) $u,v\in V(G)$, we have that uv∈E(G) $uv\in E(G)$ if and only if there are odd numbers θi ${\theta }_{i}$ such that θi≤r(u)+r(v) ${\theta }_{i}\le r(u)+r(v)$. The least integer k $k$ such that G $G$ is a k $k$‐threshold graph is called a threshold number of G $G$, and denoted by Θ(G) ${\rm{\Theta }}(G)$. The well‐known family of threshold graphs is a set of graphs G $G$ with Θ(G)≤1 ${\rm{\Theta }}(G)\le 1$. Jamison and Sprague introduced the concept of k $k$‐threshold graph, and proved that Θ(G) ${\rm{\Theta }}(G)$ exists for every graph G $G$. They further obtained a number of interesting results on Θ(G) ${\rm{\Theta }}(G)$. In addition, they also proposed several unsolved problems and conjectures, including the following two. Problem: Determine the exact threshold numbers of the complete multipartite graphs.Conjecture: For all even n≥2 $n\ge 2$, there is a graph G $G$ with Θ(G)=n ${\rm{\Theta }}(G)=n$ and Θ(Gc)=n+1 ${\rm{\Theta }}({G}^{c})=n+1$. This is equivalent to that for all odd n≥3 $n\ge 3$, there is a graph G $G$ with Θ(G)=n ${\rm{\Theta }}(G)=n$ and Θ(Gc)=n−1 ${\rm{\Theta }}({G}^{c})=n-1$, where Gc ${G}^{c}$ is the complement of G $G$.In this short paper, we give a partial solution of the problem and confirm the conjecture. [ABSTRACT FROM AUTHOR]

Let G be a graph with maximum degree Δ (G) and maximum multiplicity μ (G). Vizing and Gupta, independently, proved in the 1960s that the chromatic index of G is at most Δ (G) + μ (G). The distance between two edges e and f in G is the length of a shortest path connecting an endvertex of e and an endvertex of f. A distance- t matching is a set of edges having pairwise distance at least t. Albertson and Moore conjectured that if G is a simple graph, using the palette { 1 , ... , Δ (G) + 1 } , any precoloring on a distance-3 matching can be extended to a proper edge coloring of G. Edwards et al. proposed the following stronger conjecture: For any graph G , using the palette { 1 , ... , Δ (G) + μ (G) } , any precoloring on a distance-2 matching can be extended to a proper edge coloring of G. Girão and Kang verified the conjecture of Edwards et al. for distance-9 matchings. In this paper, we improve the required distance from 9 to 3 for multigraphs G with μ (G) ≥ 2. [ABSTRACT FROM AUTHOR]

Let G=(V(G),E(G)) be a multigraph with maximum degree Δ(G), chromatic index χ′(G), and total chromatic number χ″(G). The total coloring conjecture proposed by Behzad and Vizing, independently, states that χ″(G)≤Δ(G)+μ(G)+1 for a multigraph G, where μ(G) is the multiplicity of G. Moreover, Goldberg conjectured that χ″(G)=χ′(G) if χ′(G)≥Δ(G)+3 and noticed the conjecture holds when G is an edge‐chromatic critical graph. By assuming the Goldberg–Seymour conjecture, we show that χ″(G)=χ′(G) if χ′(G)≥max{Δ(G)+2,∣V(G)∣+1} in this note. Consequently, χ″(G)=χ′(G) if χ′(G)≥Δ(G)+2 and G has a spanning edge‐chromatic critical subgraph. [ABSTRACT FROM AUTHOR]

The multiplicity of the second‐largest eigenvalue of the adjacency matrix A(G) of a connected graph G, denoted by m(λ2,G), is the number of times of the second‐largest eigenvalue of A(G) appears. In 2019, Jiang, Tidor, Yao, Zhang, and Zhao gave an upper bound on m(λ2,G) for graphs G with bounded degrees, and applied it to solve a longstanding problem on equiangular lines. In this paper, we show that if G is a 3‐connected planar graph or 2‐connected outerplanar graph, then m(λ2,G)≤δ(G), where δ(G) is the minimum degree of G. We further prove that if G is a connected planar graph, then m(λ2,G)≤Δ(G); if G is a connected outerplanar graph, then m(λ2,G)≤max{2,Δ(G)−1}, where Δ(G) is the maximum degree of G. Moreover, these two upper bounds for connected planar graphs and outerplanar graphs, respectively, are best possible. [ABSTRACT FROM AUTHOR]

An edge cut C of a graph G is tight if | C ∩ M | = 1 for every perfect matching M of G. Barrier cuts and 2-separation cuts are called ELP-cuts , which are two important types of tight cuts in matching covered graphs. Edmonds, Lovász and Pulleyblank proved that if a matching covered graph has a nontrivial tight cut, then it also has a nontrivial ELP-cut. Carvalho, Lucchesi, and Murty made a stronger conjecture: given any nontrivial tight cut C in a matching covered graph G , there exists a nontrivial ELP-cut D in G which does not cross C. We confirm the conjecture in this paper. [ABSTRACT FROM AUTHOR]

A graph is said to be ISK4‐free if it does not contain any subdivision of K4 as an induced subgraph. Lévêque, Maffray and Trotignon conjectured that every ISK4‐free graph is 4‐colorable. In this paper, we show that this conjecture is true for the class of {ISK4, diamond, bowtie}‐free graphs, where a diamond is the graph obtained from K4 by removing one edge and a bowtie is the graph consisting of two triangles with one vertex identified. [ABSTRACT FROM AUTHOR]

Let G be a simple graph, and let χ ′ (G) and Δ (G) denote the chromatic index and the maximum degree of G , respectively. A graph G is a critical class two graph if χ ′ (G) = Δ (G) + 1 and χ ′ (H) ≤ Δ (G) for every proper subgraph H of G. Let d ‾ (G) denote the average degree of G , i.e., d ‾ (G) = 2 | E (G) | / | V (G) |. Vizing in 1968 conjectured that d ‾ (G) ≥ Δ (G) − 1 + 3 / n if G is a critical class two graph of order n. In this paper, we prove that d ‾ (G) ≥ 3 4 Δ (G) − 8 if G is a critical class two graph. Let δ (G) denote the minimum degree of G. We show that there exist two functions D and D 0 such that for any ϵ ∈ (0 , 1) , if G is a critical class two graph with Δ (G) ≥ D (ϵ) and δ (G) ≥ D 0 (ϵ) , then d ‾ (G) ≥ (1 − ϵ) Δ (G). We will give two specific functions satisfying the statement above in the paper. Moreover, we show that if G is a critical class two graph and δ (G) ≥ (log ⁡ Δ (G)) 3 4 , then d ‾ (G) ≥ Δ (G) − o (Δ (G)). [ABSTRACT FROM AUTHOR]

In the study of graph edge coloring for simple graphs, a graph G is called Δ-critical if Δ (G) = Δ , χ ′ (G) = Δ (G) + 1 and χ ′ (H) < χ ′ (G) for every proper subgraph H of G. In this paper, we prove a new adjacency result of critical graphs which allows us to control the degree of vertices with distance four. Combining this result with a previous theorem proved by the authors, we show that for every ϵ > 0 , if G is a Δ-critical graph with order n , then the average degree d ‾ (G) ≥ (1 − ϵ) Δ and the independence number α (G) ≤ (1 2 + ϵ) n provided Δ is sufficiently large. This shows that, for a Δ-critical graph G , d ‾ (G) ≥ Δ − o (Δ) and α (G) ≤ (1 / 2 + o (1)) n as Δ → ∞. [ABSTRACT FROM AUTHOR]

In 2012, Lévêque, Maffray and Trotignon conjectured that if a graph does not contain an induced subdivision of K 4 , then it is 4-colorable. Recently, Le showed that every such graph is 24-colorable. In this paper, we improve the upper bound to 8. [ABSTRACT FROM AUTHOR]

Let G be a multigraph with maximum degree Δ and chromatic index χ′. If G is bipartite then χ′=Δ. Otherwise, by a theorem of Goldberg, χ′≤Δ+1+⌊(Δ−2)/(go−1)⌋, where go denotes the odd girth of G. Stiebitz, Scheide, Toft, and Favrholdt in their book conjectured that if χ′=Δ+1+⌊(Δ−2)/(go−1)⌋ then G contains as a subgraph a ring graph R with the same chromatic index. Vizing's characterization of graphs with chromatic index attaining the Shannon's bound showed the above conjecture holds for go=3. Stiebitz et al verified the conjecture for graphs with go=5 and Δ≥10. McDonald proved the conjecture when Δ−2 is divisible by go−1. 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 go≥3 with Δ≥(go2−2go+5)/2, and the maximum degree condition is best possible. This positive result leans on the positive resolution of the Goldberg‐Seymour conjecture. [ABSTRACT FROM AUTHOR]

Let G be a graph with possible multiple edges but no loops. The density of G , denoted by ρ (G) , is defined as max H ⊂ G , | V (H) | ≥ 2 ⁡ ⌈ | E (H) | ⌊ | V (H) | / 2 ⌋ ⌉. Goldberg (1973) and Seymour (1974) independently conjectured that if the chromatic index χ ′ (G) satisfies χ ′ (G) ≥ Δ (G) + 2 then χ ′ (G) = ρ (G) , which is commonly regarded as Goldberg's conjecture. An equivalent conjecture, usually credited to Jakobsen, states that for any odd integer m ≥ 3 , if χ ′ (G) ≥ m Δ (G) m − 1 + m − 3 m − 1 then χ ′ (G) = ρ (G). The Tashkinov tree technique, a common generalization of Vizing fans and Kierstead paths for multigraphs, has emerged as the main tool to attack these two conjectures. On the other hand, Asplund and McDonald recently showed that there is a limitation to this method. In this paper, we will go beyond Tashkinov trees and provide a much larger extended structure, using which we see hope to tackle the conjecture. Applying this new technique, we show that the Goldberg's conjecture holds for graphs with Δ (G) ≤ 39 or | V (G) | ≤ 39 and the Jakobsen Conjecture holds for m ≤ 39 , where the previously known best bound is 23. We also improve a number of other related results. [ABSTRACT FROM AUTHOR]

For two graphs A and B, a graph G is called { A , B } -free if G contains neither A nor B as an induced subgraph. Let P n denote the path of order n. For nonnegative integers k, ℓ and m, let N k , ℓ , m be the graph obtained from K 3 and three vertex-disjoint paths P k + 1 , P ℓ + 1 , P m + 1 by identifying each of the vertices of K 3 with one endvertex of one of the paths. Let Z k = N k , 0 , 0 and B k , ℓ = N k , ℓ , 0 . Bedrossian characterized all pairs { A , B } of connected graphs such that every 2-connected { A , B } -free graph is Hamiltonian. All pairs appearing in the characterization involve the claw ( K 1 , 3 ) and one of N 1 , 1 , 1 , P 6 and B 1 , 2 . In this paper, we characterize connected graphs that are (i) { K 1 , 3 , Z 2 } -free but not B 1 , 1 -free, (ii) { K 1 , 3 , B 1 , 1 } -free but not P 5 -free, or (iii) { K 1 , 3 , B 1 , 2 } -free but not P 6 -free. The third result is closely related to Bedrossian's characterization. Furthermore, we apply our characterizations to some forbidden pair problems. [ABSTRACT FROM AUTHOR]

A family of finite sets is called union-closed if it contains the union of any two sets in it. The Union-Closed Sets Conjecture of Frankl from 1979 states that each union-closed family contains an element that belongs to at least half of the members of the family. In this paper, we study structural properties of union-closed families. It is known that under the inclusion relation, every union-closed family forms a lattice. We call two union-closed families isomorphic if their corresponding lattices are isomorphic. Let F be a union-closed family and ⋃ F ∈ F F be the universe of F . Among all union-closed families isomorphic to F , we develop an algorithm to find one with a maximum universe, and an algorithm to find one with a minimum universe. We also study properties of these two extremal union-closed families in connection with the Union-Closed Set Conjecture. More specifically, a lower bound of sizes of sets of a minimum counterexample to the dual version of the Union-Closed Sets Conjecture is obtained. [ABSTRACT FROM AUTHOR]

Let G be a simple graph, and let Δ (G) , d ¯ (G) and χ ′ (G) denote the maximum degree, the average degree and the chromatic index of G , respectively. We called G edge- Δ -critical if χ ′ (G) = Δ (G) + 1 and χ ′ (H) ≤ Δ (G) for every proper subgraph H of G. Vizing in 1968 conjectured that if G is an edge- Δ -critical graph of order n , then d ¯ (G) ≥ Δ (G) − 1 + 3 n. We prove that for any edge- Δ -critical graph G , d ̄ (G) ≥ min 2 2 Δ (G) − 3 − 2 2 2 + 1 , 3 Δ (G) 4 − 2 , that is, d ¯ (G) ≥ 3 4 Δ (G) − 2 if Δ (G) ≤ 75 ; 2 2 Δ (G) − 3 − 2 2 2 + 1 ≈ 0. 7388 Δ (G) − 1. 153 if Δ (G) ≥ 76. This result improves the best known bound 2 3 (Δ (G) + 2) obtained by Woodall in 2007 for Δ (G) ≥ 41. [ABSTRACT FROM AUTHOR]

Graph edge coloring has a rich theory, many applications and beautiful conjectures, and it is studied not only by mathematicians, but also by computer scientists. In this survey, written for the non-expert, we shall describe some main results and techniques and state some of the many popular conjectures in the theory. Besides known results a new basic result about brooms is obtained. [ABSTRACT FROM AUTHOR]

An r -regular graph is said to be an r -graph if | ∂ (X) | ≥ r for each odd set X ⊆ V (G) , where | ∂ (X) | denotes the set of edges with precisely one end in X. Note that every connected bridgeless cubic graph is a 3-graph. The Berge Conjecture states that every 3-graph G has five perfect matchings such that each edge of G is contained in at least one of them. Likewise, generalization of the Berge Conjecture asserts that every r -graph G has 2 r − 1 perfect matchings that covers each e ∈ E (G) at least once. A natural question to ask in the light of the Generalized Berge Conjecture is that what can we say about the proportion of edges of an r -graph that can be covered by union of t perfect matchings? In this paper we provide a lower bound to this question. We will also present a new conjecture that might help towards the proof of the Generalized Berge Conjecture. [ABSTRACT FROM AUTHOR]

A cycle of order k is called a k -cycle. A non-induced cycle is called a chorded cycle. Let n be an integer with n ≥ 4 . Then a graph G of order n is chorded pancyclic if G contains a chorded k -cycle for every integer k with 4 ≤ k ≤ n . Cream, Gould and Hirohata (Australas. J. Combin. 67 (2017), 463–469) proved that a graph of order n satisfying deg G u + deg G v ≥ n for every pair of nonadjacent vertices u , v in G is chorded pancyclic unless G is either K n 2 , n 2 or K 3 □ K 2 , the Cartesian product of K 3 and K 2 . They also conjectured that if G is Hamiltonian, we can replace the degree sum condition with the weaker density condition | E ( G ) | ≥ 1 4 n 2 and still guarantee the same conclusion. In this paper, we prove this conjecture by showing that if a graph G of order n with | E ( G ) | ≥ 1 4 n 2 contains a k -cycle, then G contains a chorded k -cycle, unless k = 4 and G is either K n 2 , n 2 or K 3 □ K 2 , Then observing that K n 2 , n 2 and K 3 □ K 2 are exceptions only for k = 4 , we further relax the density condition for sufficiently large k . [ABSTRACT FROM AUTHOR]

The structures and energetics of the cyclopentadienyliron carbonyl boronyls Cp 2 Fe 2 (BO) 2 (CO) n ( n = 3, 2, 1, 0) have been examined by density functional theory. The lowest energy Cp 2 Fe 2 (BO) 2 (CO) n ( n = 2, 0) structures are found to have bridging dioxodiborene (µ-B 2 O 2 ) ligands that can exist as cis or trans stereoisomers. Either µ-B 2 O 2 stereoisomer functions as a net three-electron donor to each iron atom in such binuclear complexes. The lowest energy Cp 2 Fe 2 (BO) 2 (CO) n ( n = 3, 1) structures resemble their isoelectronic Cp 2 Mn 2 (CO) n +2 analogues. Thus the lowest energy Cp 2 Fe 2 (BO) 2 (CO) 3 structure consists of two CpFe(BO)(CO) units joined by an Fe–Fe bond bridged by a CO group. The lowest energy Cp 2 Fe 2 (BO) 2 (CO) structure is a singlet triply bridged structure with a short ∼2.17 Å Fe Fe distance suggesting a formal triple bond. This latter structure is very similar to the experimental structure of the isoelectronic Cp* 2 Mn 2 (µ-CO) 3 , synthesized by Hermann and coworkers and shown by X-ray crystallography to be a triply bridged structure with a ∼2.17 Å Mn Mn distance. [ABSTRACT FROM AUTHOR]

Let G be an n-vertex simple graph, and let [ABSTRACT FROM AUTHOR]

Vizing conjectured that every edge chromatic critical graph contains a 2-factor. Believing that stronger properties hold for this class of graphs, Luo and Zhao (2013) showed that every edge chromatic critical graph of order n with maximum degree at least 6 n 7 is Hamiltonian. Furthermore, Luo et al. (2016) proved that every edge chromatic critical graph of order n with maximum degree at least 4 n 5 is Hamiltonian. In this paper, we prove that every edge chromatic critical graph of order n with maximum degree at least 3 n 4 is Hamiltonian. Our approach is inspired by the recent development of Kierstead path and Tashkinov tree techniques for multigraphs. [ABSTRACT FROM AUTHOR]

For a vertex u in a graph and a given positive integer k , let M k (u) denote the set of vertices whose distance from u is at most k. A graph satisfies the local Dirac's condition if the degree of each vertex u in it is at least | M 2 (u) | 2. Asratian et al. disproved that a connected graph G on at least three vertices is Hamiltonian if G satisfies the local Dirac's condition. In this paper, we prove that if a connected graph G on at least three vertices satisfies the local Dirac's condition, then G contains a 2-factor. Our result is best possible. [ABSTRACT FROM AUTHOR]

Different spatial locations provide different external conditions for root decomposition, while species and root order cause obvious differences in root substrate quality. Both differences in internal and external conditions may determine root decomposition rate. We explored the effects of decomposition position, root order, and species differences on root decomposition, and determined the role of manganese (Mn) in root decomposition. We conducted a fine root decomposition experiment using roots from Schima superba , Cleyera japonica, and Eurya loquaiana (separated into orders 1−3, 4−5, and 6) in the litter layer, and at 0−10 cm, 20−30 cm, and 40−50 cm soil depth in a subtropical forest. Root mass and concentration of C, N, P, Mn, condensed tannins and total phenolics were measured during two years of decomposition. Root decomposition rates decreased with increasing soil depth for all root samples. Compared to decomposition at 0−10 cm soil depth, remaining mass (% of initial) declined by 7%–34% in the litter layer and increased by 17%–37% at 40−50 cm soil depth. Lower-order roots had a higher decomposition rate than higher-order roots in the litter layer, but at 40−50 cm soil depth, we observed the opposite. Root litter Mn concentration and remaining mass were negatively correlated during the whole decomposition period including the early, middle, and late stages. Initial root Mn content was negatively correlated with remaining mass after two years of decomposition in the litter layer, and at 20−30 cm, 40−50 cm soil depth. However, no significant relationship between mass remaining and initial root N, P, condensed tannins and total phenolics were observed in the subsoil. Variance partitioning showed that the soil layer contributes significantly to the variance in remaining root mass, C, and Mn, whereas root order group contributed more than the soil layer to remaining root N and P. Our results indicate that soil depth is more important than root order for fine root decomposition rate at a site scale. Relative root decomposition rate between lower- and higher-order roots depends on the decomposition environment. Overall, this study strongly suggests that root Mn concentration (whether in initial or other decomposition stages) was much more consistently correlated with mass remaining than traditional predictors of N, P, condensed tannins, or total phenolics. Root Mn concentration greatly indicates root decomposition rates across soil layers, root orders, and species. Initial root Mn concentration and Mn supply capacity of the decomposition environment jointly control root decomposition rates throughout the decomposition process. • Fine root was decomposed by root order in litter layer, and at different soil depth. • Root Mn content and remaining mass were negatively correlated during decomposition. • Root decomposition rate is more affected by soil depth than root order. • Root Mn content controls root decomposition rates across soil layer and root order. [ABSTRACT FROM AUTHOR]

A graph is called $$2K_2$$ -free if it does not contain two independent edges as an induced subgraph. Gao and Pasechnik conjectured that every $$\frac{3}{2}$$ -tough $$2K_2$$ -free graph with at least three vertices has a spanning trail with maximum degree at most 4. In this paper, we confirm this conjecture. We also provide examples for all $$t < \frac{5}{4}$$ of t-tough graphs that do not have a spanning trail with maximum degree at most 4. [ABSTRACT FROM AUTHOR]

A Halin graph is constructed from a plane embedding of a tree with no vertices of degree 2 by adding a cycle through its leaves in the natural order determined by the embedding. Halin graphs satisfy interesting properties. However, to our knowledge, there are no results giving a positive answer for 'spanning Halin subgraph problem' (i.e., which graph has a Halin graph as a spanning subgraph) except for a conjecture by Lovász and Plummer which states that every 4-connected plane triangulation contains a spanning Halin subgraph. In this paper, we investigate the characterization of forbidden pairs guaranteeing the existence of a spanning Halin subgraph. In particular, we show that the set of such pairs is a very small class. Also, we show that $$\{ K_{1,3}, P_5 \}$$ belongs to the set, but neither $$\{ K_{1,4}, P_5 \}$$ nor $$\{ K_{1,3}, P_6 \}$$ belongs to the set. [ABSTRACT FROM AUTHOR]

In 1966 Gallai asked whether all longest paths in a connected graph have nonempty intersection. This is not true in general and various counterexamples have been found. However, the answer to Gallai’s question is positive for several well-known classes of graphs, as for instance connected outerplanar graphs, connected split graphs, and 2-trees. A graph is series–parallel if it does not contain K 4 as a minor. Series–parallel graphs are also known as partial 2-trees, which are arbitrary subgraphs of 2-trees. We present two independent proofs that every connected series–parallel graph has a vertex that is common to all of its longest paths. Since 2-trees are maximal series–parallel graphs, and outerplanar graphs are also series–parallel, our result captures these two classes in one proof and strengthens them to a larger class of graphs. We also describe how one such vertex can be found in linear time. [ABSTRACT FROM AUTHOR]

• Obtain that if α (G) ≤ k + ⌈ k + 1 r − 3 ⌉ − ⌊ 1 | r − k − 3 | + 1 ⌋ with k ≥ 2 and r ≥ 4 , then every 2-connected K 1 , r -free graph G contains a spanning tree with at most k leaves and the upper bound of α (G) is best possible. • Prove that if a connected K 1 , 4 -free graph G satisfies that α (G) ≤ 2 k + 5 , then G contains either a spanning tree with at most k branch vertices or a block B with α (B) ≤ 2. • Pose a related conjecture for 2-connected claw-free graphs. A vertex with degree one and a vertex with degree at least three are called a leaf and a branch vertex in a tree, respectively. In this paper, we obtain that every 2-connected K 1 , r -free graph G contains a spanning tree with at most k leaves if α (G) ≤ k + ⌈ k + 1 r − 3 ⌉ − ⌊ 1 | r − k − 3 | + 1 ⌋ , where k ≥ 2 and r ≥ 4. The upper bound is best possible. Furthermore, we prove that if a connected K 1 , 4 -free graph G satisfies that α (G) ≤ 2 k + 5 , then G contains either a spanning tree with at most k branch vertices or a block B with α (B) ≤ 2. A related conjecture for 2-connected claw-free graphs is also posed. [ABSTRACT FROM AUTHOR]

The square of a graph is obtained by adding additional edges joining all pair of vertices of distance two in the original graph. Particularly, if $$C$$ is a hamiltonian cycle of a graph $$G$$ , then the square of $$C$$ is called a hamiltonian square of $$G$$ . In this paper, we characterize all possible forbidden pairs, which implies the containment of a hamiltonian square, in a 4-connected graph. The connectivity condition is necessary as, except $$K_3$$ and $$K_4$$ , the square of a cycle is always 4-connected. [ABSTRACT FROM AUTHOR]

Chvátal and Erdős proved a well-known result that the graph $$G$$ with connectivity $$\kappa (G)$$ not less than its independence number $$\alpha (G)$$ [ $$\alpha (G)+1$$ , $$\alpha (G)-1$$ , respectively] is Hamiltonian (traceable, Hamiltonian-connected, respectively). In this paper, we strengthen the Chvátal-Erdős theorem to the following: Let $$G$$ be a simple 2-connected graph of order large enough such that $$\alpha (G)\le \kappa (G)+1$$ [ $$\alpha (G)\le \kappa (G)+2$$ , $$\alpha (G)\le \kappa (G),$$ respectively] and such that the number of maximum independent sets of cardinality $$\kappa (G)+1$$ [ $$\kappa (G)+2$$ , $$\kappa (G)$$ , respectively] is at most $$n-2\kappa (G)$$ [ $$n-2\kappa (G)-1$$ , $$n-2\kappa (G)+1$$ , respectively]. Then $$G$$ is either Hamiltonian (traceable, Hamiltonian-connected, respectively) or a subgraph of $$K_{k}+((kK_1)\cup K_{n-2k})$$ [ $$K_{k}+((k+1)K_1\cup K_{n-2k-1})$$ , $$K_{k}+((k-1)K_1\cup K_{n-2k+1})$$ , respectively]. [ABSTRACT FROM AUTHOR]

For a simple graph G , denote by n , Δ (G) , and χ ′ (G) its order, maximum degree, and chromatic index, respectively. A graph G is edge-chromatic critical if χ ′ (G) = Δ (G) + 1 and χ ′ (H) < χ ′ (G) for every proper subgraph H of G. Let G be an n -vertex connected regular class 1 graph, and let G ⁎ be obtained from G by splitting one vertex of G into two vertices. Hilton and Zhao in 1997 conjectured that G ⁎ must be edge-chromatic critical if Δ (G) > n / 3 , and they verified this when Δ (G) ≥ n 2 (7 − 1) ≈ 0.82 n. In this paper, we prove it for Δ (G) ≥ 0.75 n. [ABSTRACT FROM AUTHOR]

A broom is a tree obtained by subdividing one edge of the star an arbitrary number of times. In (E. Flandrin, T. Kaiser, R. Kužel, H. Li and Z. Ryjáček, Neighborhood Unions and Extremal Spanning Trees, Discrete Math 308 (2008), 2343-2350) Flandrin et al. posed the problem of determining degree conditions that ensure a connected graph G contains a spanning tree that is a broom. In this article, we give one solution to this problem by demonstrating that if G is a connected graph of order [ABSTRACT FROM AUTHOR]

A set F of edges in a digraph D is called a directed cut if there exists a nontrivial partition [ABSTRACT FROM AUTHOR]

Abstract: We show that if G is a graph such that every edge is in at least two triangles, then G contains a spanning tree with no vertex of degree 2 (a homeomorphically irreducible spanning tree). This result was originally asked in a question format by Albertson, Berman, Hutchinson, and Thomassen in 1979, and then conjectured to be true by Archdeacon in 2009. [Copyright &y& Elsevier]

Abstract: The class of graphs with no -minors, , contains all planar graphs and plays an important role in graph minor theory. In 1992, Seymour and Thomas conjectured the existence of a function and a constant , such that every 3-connected n-vertex graph with no -minors, , contains a cycle of length at least . The purpose of this paper is to confirm this conjecture with and . [Copyright &y& Elsevier]

Abstract: A path in a graph is called extendable if it is a proper subpath of another path. A graph is locally connected if every neighborhood induces a connected subgraph. We show that, for each graph of order , there exists a threshold number such that every path of order smaller than is extendable and there exists a non-extendable path of order for each if satisfies any one of the following three conditions: [ ] the degree sum for any two nonadjacent vertices and ; [ ] -free and for every cut set of ; [ ] connected, locally connected, and -free where and denote a path of order and a complete bipartite graph with and vertices in each color class, respectively. [Copyright &y& Elsevier]

Abstract: Let be a graph of order . An even squared Hamiltonian cycle (ESHC) of is a Hamiltonian cycle of with chords for all (where for ). When is even, an ESHC contains all bipartite -regular graphs of order . We prove that there is a positive integer such that for every graph of even order , if the minimum degree is , then contains an ESHC. We show that the condition of being even cannot be dropped and the constant cannot be replaced by . Our results can be easily extended to even th powered Hamiltonian cycles for all . [Copyright &y& Elsevier]

Abstract: For an integer with and a pair of connected graphs and of order at least three, we say that is a -forbidden pair if every -connected -free graph, except possibly for a finite number of exceptions, is Hamiltonian. If no exception arises, is said to be a strong -forbidden pair. The 2-forbidden pairs and the strong 2-forbidden pairs are determined by Faudree and Gould (1997) and Bedrossian (1991) , respectively. All of them contain . In this paper, we prove that is a strong -forbidden pair, which shows that is not always necessary in a -forbidden pair for . On the other hand, we prove that each -forbidden pair contains for some . We also discuss several other Hamiltonian properties of -connected -free graphs. [Copyright &y& Elsevier]

Abstract: The path spectrum of a graph is the set of lengths of all maximal paths in the graph. A set of positive integers is spectral if it is the path spectrum of a tree. We characterize the spectral sets containing at most two odd integers (and arbitrarily many even ones) and obtain several necessary conditions for a set to be spectral. We show that for each even integer at least of all subsets of the set are spectral and conjecture that all the subsets with at least integers are spectral. [ABSTRACT FROM AUTHOR]

Abstract: A nonincreasing sequence of nonnegative integers is graphic if there is a (simple) graph of order having degree sequence . In this case, is said to realize . For a given graph , a graphic sequence is potentially -graphic if there is some realization of containing as a (weak) subgraph. Let denote the sum of the terms of . For a graph and , is defined as the smallest even integer so that every -term graphic sequence with is potentially -graphic. Let denote the complete partite graph such that each partite set has exactly vertices. We show that and obtain the exact value of for sufficiently large. Consequently, we obtain the exact value of for sufficiently large. [Copyright &y& Elsevier]

Let G be an infinite graph embedded in a closed 2-manifold, such that each open face of the embedding is homeomorphic to an open disk and is bounded by finite number of edges. For each vertex x of G, define the combinatorial curvature as that of [8], where d( x) is the degree of x, F( x) is the multiset of all open faces σ in the embedding such that the closure $$\bar\sigma$$ contains x (the multiplicity of σ is the number of times that x is visited along ∂σ), and |σ| is the number of sides of edges bounding the face σ. In this paper, we first show that if the absolute total curvature ∑ x∈ V( G) |Φ G ( x)| is finite, then G has only finite number of vertices of non-vanishing curvature. Next we present a Gauss-Bonnet formula for embedded infinite graphs with finite number of accumulation points. At last, for a finite simple graph G with 3 ≤ d G ( x) < ∞ and Φ G ( x) > 0 for every x ∈ V( G), we have (i) if G is embedded in a projective plane and #( V( G)) = n ≥ 1722, then G is isomorphic to the projective wheel P n ; (ii) if G is embedded in a sphere and #( V( G)) = n ≥ 3444, then G is isomorphic to the sphere annulus either A n or B n ; and (iii) if d G ( x) = 5 for all x ∈ V( G), then there are only 49 possible embedded plane graphs and 16 possible embedded projective plane graphs. [ABSTRACT FROM AUTHOR]

Abstract: A graph G is k-linked if G has at least 2k vertices, and for every sequence of distinct vertices, G contains k vertex-disjoint paths such that joins and for . Moreover, the above defined k-linked graph G is modulo -linked if, in addition, for any k-tuple of natural numbers, the paths can be chosen such that has length modulo for . Thomassen showed that, for each k-tuple of odd positive integers, there exists a natural number such that every -connected graph is modulo -linked. For , he showed in another article that there exists a natural number such that every -connected graph G is modulo -linked or there is such that and is a bipartite graph, where is a k-tuple. We showed that for every k-tuple of odd positive integers. We then extend the result to allow some be even integers. Let be a k-tuple of natural numbers and such that is odd for each i with . If G is -connected, then either G has a vertex set X of order at most such that is bipartite or G is modulo -linked, where Our results generalize several known results on parity-linked graphs. [Copyright &y& Elsevier]

Let G be a 2-connected graph of order n satisfying α(G) = a ≤ κ(G), where α(G) and κ(G) are the independence number and the connectivity of G, respectively, and let r(m; n) denote the Ramsey number. The well-known Chvátal-Erdős Theorem states that G has a hamiltonian cycle. In this paper, we extend this theorem, and prove that G has a 2-factor with a specified number of components if n is sufficiently large. More precisely, we prove that (1) if n ≥ k · r(a + 4, a + 1), then G has a 2-factor with k components, and (2) if n ≥ r(2a + 3, a + 1) + 3(k - 1), then G has a 2-factor with k components such that all components but one have order three. [ABSTRACT FROM AUTHOR]

Abstract: Let G be a graph, the neighborhood of for each , and for each . For any two positive integers s and t, we prove that there exists a least positive integer such that every -connected graph G of order is hamiltonian if for every two disjoint independent vertex sets S, T with and . [Copyright &y& Elsevier]