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 .     

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.     

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.     

Large Induced Forests in Graphs

In this article, we prove three theorems. The first is that every connected graph of order n and size m has an induced forest of order at least with equality if and only if such a graph is obtained from a tree by expanding every vertex to a clique of order either 4 or 5. This improves the previous lower bound of Alon–Kahn–Seymour for , and implies that such a graph has an induced forest of order at least for . This latter result relates to the conjecture of Albertson and Berman that every planar graph of order n has an induced forest of order at least . The second is that every connected triangle‐free graph of order n and size m has an induced forest of order at least . This bound is sharp by the cube and the Wagner graph. It also improves the previous lower bound of Alon–Mubayi–Thomas for , and implies that such a graph has an induced forest of order at least for . This latter result relates to the conjecture of Akiyama and Watanabe that every bipartite planar graph of order n has an induced forest of order at least . The third is that every connected planar graph of order n and size m with girth at least 5 has an induced forest of order at least with equality if and only if such a graph is obtained from a tree by expanding every vertex to one of five specific graphs. This implies that such a graph has an induced forest of order at least , where was conjectured to be the best lower bound by Kowalik, Lu?ar, and ?krekovski.     

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 .     

Smallest graphs with given generalized quaternion automorphism group

For , a smallest graph whose automorphism group is isomorphic to the generalized quaternion group is constructed. If , then such a graph has vertices and edges. In the special case when , a smallest graph has 16 vertices but 44 edges.     

List Coloring with a Bounded Palette

Král' and Sgall (J Graph Theory 49(3) (2005), 177–186) introduced a refinement of list coloring where every color list must be subset to one predetermined palette of colors. We call this ‐choosability when the palette is of size at most ? and the lists must be of size at least k . They showed that, for any integer , there is an integer , satisfying as , such that, if a graph is ‐choosable, then it is C‐choosable, and asked if C is required to be exponential in k . We demonstrate it must satisfy . For an integer , if is the least integer such that a graph is ‐choosable if it is ‐choosable, then we more generally supply a lower bound on , one that is super‐polynomial in k if , by relation to an extremal set theoretic property. By the use of containers, we also give upper bounds on that improve on earlier bounds if .     

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.     

The decycling number and maximum genus of cubic graphs

Let and denote the minimum size of a decycling set and maximum genus of a graph G, respectively. For a connected cubic graph G of order n, it is shown that . Applying the formula, we obtain some new results on the decycling number and maximum genus of cubic graphs. Furthermore, it is shown that the number of vertices of a decycling set S in a k‐regular graph G is , where c and are the number of components of and the number of edges in , respectively. Therefore, S is minimum if and only if is minimum. As an application, this leads to a lower bound for of a k‐regular graph G. In many cases this bound may be sharp.     

Edge‐transitive homogeneous factorizations of complete uniform hypergraphs

For a finite set V and a positive integer k with , letting be the set of all k‐subsets of V, the pair is called the complete k‐hypergraph on V, while each k‐subset of V is called an edge. A factorization of the complete k‐hypergraph of index , simply a ‐factorization of order n, is a partition of the edges into s disjoint subsets such that each k‐hypergraph , called a factor, is a spanning subhypergraph of . Such a factorization is homogeneous if there exist two transitive subgroups G and M of the symmetric group of degree n such that G induces a transitive action on the set and M lies in the kernel of this action. In this article, we give a classification of homogeneous factorizations of that admit a group acting transitively on the edges of . It is shown that, for and , there exists an edge‐transitive homogeneous ‐factorization of order n if and only if is one of (32, 3, 5), (32, 3, 31), (33, 4, 5), , and , where and q is a prime power with .     

Strengthening Theorems of Dirac and Erdős on Disjoint Cycles

Let be an integer, be the set of vertices of degree at least 2k in a graph G , and be the set of vertices of degree at most in G . In 1963, Dirac and Erd?s proved that G contains k (vertex) disjoint cycles whenever . The main result of this article is that for , every graph G with containing at most t disjoint triangles and with contains k disjoint cycles. This yields that if and , then G contains k disjoint cycles. This generalizes the Corrádi–Hajnal Theorem, which states that every graph G with and contains k disjoint cycles.     

Extensions of Fractional Precolorings Show Discontinuous Behavior

We study the following problem: given a real number k and an integer d, what is the smallest ε such that any fractional ‐precoloring of vertices at pairwise distances at least d of a fractionally k‐colorable graph can be extended to a fractional ‐coloring of the whole graph? The exact values of ε were known for and any d. We determine the exact values of ε for if , and if , and give upper bounds for if , and if . Surprisingly, ε viewed as a function of k is discontinuous for all those values of d.     

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.     

Calculating Ramsey Numbers by Partitioning Colored Graphs

In this article we prove a new result about partitioning colored complete graphs and use it to determine certain Ramsey numbers exactly. The partitioning theorem we prove is that for , in every edge coloring of with the colors red and blue, it is possible to cover all the vertices with k disjoint red paths and a disjoint blue balanced complete ‐partite graph. When the coloring of is connected in red, we prove a stronger result—that it is possible to cover all the vertices with k red paths and a blue balanced complete ‐partite graph. Using these results we determine the Ramsey number of an n‐vertex path, , versus a balanced complete t‐partite graph on vertices, , whenever . We show that in this case , generalizing a result of Erd?s who proved the case of this result. We also determine the Ramsey number of a path versus the power of a path . We show that , solving a conjecture of Allen, Brightwell, and Skokan.     

Low Polynomial Exclusion of Planar Graph Patterns

The celebrated grid exclusion theorem states that for every h‐vertex planar graph H , there is a constant such that if a graph G does not contain H as a minor then G has treewidth at most . We are looking for patterns of H where this bound can become a low degree polynomial. We provide such bounds for the following parameterized graphs: the wheel , the double wheel , any graph of pathwidth at most 2 , and the yurt graph .     

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 .     

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.     

Clique minors in double‐critical graphs

A connected t‐chromatic graph G is double‐critical if is ‐colorable for each edge . A long‐standing conjecture of Erdős and Lovász that the complete graphs are the only double‐critical t‐chromatic graphs remains open for all . Given the difficulty in settling Erdős and Lovász's conjecture and motivated by the well‐known Hadwiger's conjecture, Kawarabayashi, Pedersen, and Toft proposed a weaker conjecture that every double‐critical t‐chromatic graph contains a minor and verified their conjecture for . Albar and Gonçalves recently proved that every double‐critical 8‐chromatic graph contains a K₈ minor, and their proof is computer assisted. In this article, we prove that every double‐critical t‐chromatic graph contains a minor for all . Our proof for is shorter and computer free.