Edge‐Disjoint Spanning Trees,Edge Connectivity,and Eigenvalues in Graphs

Let and denote the second largest eigenvalue and the maximum number of edge‐disjoint spanning trees of a graph G, respectively. Motivated by a question of Seymour on the relationship between eigenvalues of a graph G and bounds of , Cioab? and Wong conjectured that for any integers and a d‐regular graph G, if , then . They proved the conjecture for , and presented evidence for the cases when . Thus the conjecture remains open for . We propose a more general conjecture that for a graph G with minimum degree , if , then . In this article, we prove that for a graph G with minimum degree δ, each of the following holds.

• (i) For , if and , then .
• (ii) For , if and , then .

Our results sharpen theorems of Cioab? and Wong and give a partial solution to Cioab? and Wong's conjecture and Seymour's problem. We also prove that for a graph G with minimum degree , if , then the edge connectivity is at least k, which generalizes a former result of Cioab?. As corollaries, we investigate the Laplacian and signless Laplacian eigenvalue conditions on and edge connectivity.     

Smallest domination number and largest independence number of graphs and forests with given degree sequence

For a sequence d of nonnegative integers, let and be the sets of all graphs and forests with degree sequence d, respectively. Let , , , and where is the domination number and is the independence number of a graph G. Adapting results of Havel and Hakimi, Rao showed in 1979 that can be determined in polynomial time. We establish the existence of realizations with , and with and that have strong structural properties. This leads to an efficient algorithm to determine for every given degree sequence d with bounded entries as well as closed formulas for and .     

Nonseparating Cycles Avoiding Specific Vertices

Thomassen proved that every ‐connected graph G contains an induced cycle C such that is k‐connected, establishing a conjecture of Lovász. In general, one could ask the following question: For any positive integers , does there exist a smallest positive integer such that for any ‐connected graph G, any with , and any , there is an induced cycle C in such that and is l‐connected? The case when is a well‐known conjecture of Lovász that is still open for . In this article, we prove and . We also consider a weaker version: For any positive integers , is there a smallest positive integer such that for every ‐connected graph G and any with , there is an induced cycle C in such that is l‐connected? The case when was studied by Thomassen. We prove and .     

Hamiltonicity and Degrees of Adjacent Vertices in Claw‐Free Graphs

For a graph H , let for every edge . For and , let be a set of k‐edge‐connected K₃‐free graphs of order at most r and without spanning closed trails. We show that for given and ε, if H is a k‐connected claw‐free graph of order n with and , and if n is sufficiently large, then either H is Hamiltonian or the Ryjác?ek's closure where G is an essentially k‐edge‐connected K₃‐free graph that can be contracted to a graph in . As applications, we prove:

• (i) For , if and if and n is sufficiently large, then H is Hamiltonian.
• (ii) For , if and n is sufficiently large, then H is Hamiltonian.

These bounds are sharp. Furthermore, since the graphs in are fixed for given p and can be determined in a constant time, any improvement to (i) or (ii) by increasing the value of p and so enlarging the number of exceptions can be obtained computationally.     

A simple formula for the number of spanning trees of line graphs

Suppose is a loopless graph and is the graph obtained from G by subdividing each of its edges k () times. Let be the set of all spanning trees of G, be the line graph of the graph and be the number of spanning trees of . By using techniques from electrical networks, we first obtain the following simple formula: Then we find it is in fact equivalent to a complicated formula obtained recently using combinatorial techniques in [F. M. Dong and W. G. Yan, Expression for the number of spanning trees of line graphs of arbitrary connected graphs, J. Graph Theory. 85 (2017) 74–93].     

A Relaxed Version of the Erdős–Lovász Tihany Conjecture

The Erd?s–Lovász Tihany conjecture asserts that every graph G with ) contains two vertex disjoint subgraphs G ₁ and G ₂ such that and . Under the same assumption on G , we show that there are two vertex disjoint subgraphs G ₁ and G ₂ of G such that (a) and or (b) and . Here, is the chromatic number of is the clique number of G , and col(G ) is the coloring number of G .     

Polychromatic colorings of complete graphs with respect to 1‐, 2‐factors and Hamiltonian cycles

If G is a graph and is a set of subgraphs of G, then an edge‐coloring of G is called ‐polychromatic if every graph from gets all colors present in G. The ‐polychromatic number of G, denoted , is the largest number of colors such that G has an ‐polychromatic coloring. In this article, is determined exactly when G is a complete graph and is the family of all 1‐factors. In addition is found up to an additive constant term when G is a complete graph and is the family of all 2‐factors, or the family of all Hamiltonian cycles.     

Packing Countably Many Branchings with Prescribed Root‐Sets in Infinite Digraphs

We generalize an unpublished result of C. Thomassen. Let be a digraph and let be a multiset of subsets of V in such a way that any backward‐infinite path in D meets all the sets . We show that if all is simultaneously reachable from the sets by edge‐disjoint paths, then there exists a system of edge‐disjoint spanning branchings in D where the root‐set of is .     

Strong Chromatic Index of Sparse Graphs

A coloring of the edges of a graph G is strong if each color class is an induced matching of G. The strong chromatic index of G, denoted by , is the least number of colors in a strong edge coloring of G. Chang and Narayanan (J Graph Theory 73(2) (2013), 119–126) proved recently that for a 2‐degenerate graph G. They also conjectured that for any k‐degenerate graph G there is a linear bound , where c is an absolute constant. This conjecture is confirmed by the following three papers: in (G. Yu, Graphs Combin 31 (2015), 1815–1818), Yu showed that . In (M. Debski, J. Grytczuk, M. Sleszynska‐Nowak, Inf Process Lett 115(2) (2015), 326–330), D?bski, Grytczuk, and ?leszyńska‐Nowak showed that . In (T. Wang, Discrete Math 330(6) (2014), 17–19), Wang proved that . If G is a partial k‐tree, in (M. Debski, J. Grytczuk, M. Sleszynska‐Nowak, Inf Process Lett 115(2) (2015), 326–330), it is proven that . Let be the line graph of a graph G, and let be the square of the line graph . Then . We prove that if a graph G has an orientation with maximum out‐degree k, then has coloring number at most . If G is a k‐tree, then has coloring number at most . As a consequence, a graph with has , and a k‐tree G has .     

On the Structure of Graphs with Given Odd Girth and Large Minimum Degree

We study minimum degree conditions for which a graph with given odd girth has a simple structure. For example, the classical work of Andrásfai, Erd?s, and Sós implies that every n‐vertex graph with odd girth and minimum degree bigger than must be bipartite. We consider graphs with a weaker condition on the minimum degree. Generalizing results of Häggkvist and of Häggkvist and Jin for the cases and 3, we show that every n‐vertex graph with odd girth and minimum degree bigger than is homomorphic to the cycle of length . This is best possible in the sense that there are graphs with minimum degree and odd girth that are not homomorphic to the cycle of length . Similar results were obtained by Brandt and Ribe‐Baumann.     

A relaxation of the strong Bordeaux Conjecture

Let be k nonnegative integers. A graph G is ‐colorable if the vertex set can be partitioned into k sets , such that the subgraph , induced by , has maximum degree at most for . Let denote the family of plane graphs with neither adjacent 3‐cycles nor 5‐cycles. Borodin and Raspaud (2003) conjectured that each graph in is (0, 0, 0)‐colorable (which was disproved very recently). In this article, we prove that each graph in is (1, 1, 0)‐colorable, which improves the results by Xu (2009) and Liu‐Li‐Yu (2016).     

Ramsey Results for Cycle Spectra

Let denote the set of lengths of cycles of a graph G of order n and let denote the complement of G. We show that if , then contains all odd ? with and all even ? with , where and denote the maximum odd and the maximum even integer in , respectively. From this we deduce that the set contains at least integers, which is sharp.     

A Density Turán Theorem

Let F be a graph that contains an edge whose deletion reduces its chromatic number. For such a graph F , a classical result of Simonovits from 1966 shows that every graph on vertices with more than edges contains a copy of F . In this article we derive a similar theorem for multipartite graphs. For a graph H and an integer , let be the minimum real number such that every ?‐partite graph whose edge density between any two parts is greater than contains a copy of H . Our main contribution in this article is to show that for all sufficiently large if and only if H admits a vertex‐coloring with colors such that all color classes but one are independent sets, and the exceptional class induces just a matching. When H is a complete graph, this recovers a result of Pfender (Combinatorica 32 (2012), 483–495). We also consider several extensions of Pfender's result.     

Complete graph immersions and minimum degree

An immersion of a graph H in another graph G is a one‐to‐one mapping and a collection of edge‐disjoint paths in G, one for each edge of H, such that the path corresponding to the edge has endpoints and . The immersion is strong if the paths are internally disjoint from . We prove that every simple graph of minimum degree at least contains a strong immersion of the complete graph . This improves on previously known bound of minimum degree at least 200t obtained by DeVos et al. Our result supports a conjecture of Lescure and Meyniel (also independently proposed by Abu‐Khzam and Langston), which is the analogue of famous Hadwiger’s conjecture for immersions and says that every graph without a ‐immersion is ‐colorable.     

Sufficient conditions for the existence of a path‐factor which are related to odd components

In this article, we are concerned with sufficient conditions for the existence of a ‐factor. We prove that for , there exists such that if a graph G satisfies for all , then G has a ‐factor, where is the number of components C of with . On the other hand, we construct infinitely many graphs G having no ‐factor such that for all .     

Dynamic choosability of triangle‐free graphs and sparse random graphs

Ther‐dynamic choosability of a graph G, written , is the least k such that whenever each vertex is assigned a list of at least k colors a proper coloring can be chosen from the lists so that every vertex v has at least neighbors of distinct colors. Let ch(G) denote the choice number of G. In this article, we prove when is bounded. We also show that there exists a constant C such that the random graph with almost surely satisfies . Also if G is a triangle‐free regular graph, then we have .     

Achromatic and Harmonious Colorings of Circulant Graphs

A proper vertex coloring of a graph G is achromatic (respectively harmonious) if every two colors appear together on at least one (resp. at most one) edge. The largest (resp. the smallest) number of colors in an achromatic (resp. a harmonious) coloring of G is called the achromatic (resp. harmonious chromatic) number of G and denoted by (resp. ). For a finite set of positive integers and a positive integer n, a circulant graph, denoted by , is an undirected graph on the set of vertices that has an edge if and only if either or is a member of (where substraction is computed modulo n). For any fixed set , we show that is asymptotically equal to , with the error term . We also prove that is asymptotically equal to , with the error term . As corollaries, we get results that improve, for a fixed k, the previously best estimations on the lengths of a shortest k‐radius sequence over an n‐ary alphabet (i.e., a sequence in which any two distinct elements of the alphabet occur within distance k of each other) and a longest packing k‐radius sequence over an n‐ary alphabet (which is a dual counterpart of a k‐radius sequence).     

Excluding pairs of tournaments

The Erdős–Hajnal conjecture states that for every given undirected graph H there exists a constant such that every graph G that does not contain H as an induced subgraph contains a clique or a stable set of size at least . The conjecture is still open. Its equivalent directed version states that for every given tournament H there exists a constant such that every H‐free tournament T contains a transitive subtournament of order at least . In this article, we prove that for several pairs of tournaments, H₁ and H₂, there exists a constant such that every ‐free tournament T contains a transitive subtournament of size at least . In particular, we prove that for several tournaments H, there exists a constant such that every ‐free tournament T, where stands for the complement of H, has a transitive subtournament of size at least . To the best of our knowledge these are first nontrivial results of this type.