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 .     

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 .     

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 .     

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.     

More on the Bipartite Decomposition of Random Graphs

For a graph , let denote the minimum number of pairwise edge disjoint complete bipartite subgraphs of G so that each edge of G belongs to exactly one of them. It is easy to see that for every graph G , , where is the maximum size of an independent set of G . Erd?s conjectured in the 80s that for almost every graph G equality holds, that is that for the random graph , with high probability, that is with probability that tends to 1 as n tends to infinity. The first author showed that this is slightly false, proving that for most values of n tending to infinity and for , with high probability. We prove a stronger bound: there exists an absolute constant so that with high probability.     

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.     

Full subgraphs

Let be a graph of density p on n vertices. Following Erdős, Łuczak, and Spencer, an m‐vertex subgraph H of G is called full if H has minimum degree at least . Let denote the order of a largest full subgraph of G. If is a nonnegative integer, define Erdős, Łuczak, and Spencer proved that for , In this article, we prove the following lower bound: for , Furthermore, we show that this is tight up to a multiplicative constant factor for infinitely many p near the elements of . In contrast, we show that for any n‐vertex graph G, either G or contains a full subgraph on vertices. Finally, we discuss full subgraphs of random and pseudo‐random graphs, and several open problems.     

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.     

On Generalized Ramsey Numbers for 3‐Uniform Hypergraphs

The well‐known Ramsey number is the smallest integer n such that every ‐free graph of order n contains an independent set of size u. In other words, it contains a subset of u vertices with no K₂. Erd?s and Rogers introduced a more general problem replacing K₂ by  for . Extending the problem of determining Ramsey numbers they defined the numbers where the minimum is taken over all ‐free graphs G of order n. In this note, we study an analogous function for 3‐uniform hypergraphs. In particular, we show that there are constants c₁ and c₂ depending only on s such that      

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 .     

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 .     

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.     

On an anti‐Ramsey threshold for sparse graphs with one triangle

For graphs G and H, let  denote the property that for every proper edge‐coloring of G (with an arbitrary number of colors) there is a rainbow copy of H in G, that is, a copy of H with no two edges of the same color. The authors (2014) proved that, for every graph H, the threshold function  of this property for the binomial random graph  is asymptotically at most , where denotes the so‐called maximum 2‐density of H. Nenadov et al. (2014) proved that if H is a cycle with at least  seven vertices or a complete graph with at least 19 vertices, then . We show that there exists a fairly rich, infinite family of graphs F containing a triangle such that if for suitable constants and , where , then almost surely. In particular, for any such graph F.     

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.     

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.     

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 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 .     

Dominating sets inducing large components in maximal outerplanar graphs

For a maximal outerplanar graph G of order n at least three, Matheson and Tarjan showed that G has domination number at most . Similarly, for a maximal outerplanar graph G of order n at least five, Dorfling, Hattingh, and Jonck showed, by a completely different approach, that G has total domination number at most unless G is isomorphic to one of two exceptional graphs of order 12. We present a unified proof of a common generalization of these two results. For every positive integer k, we specify a set of graphs of order at least and at most such that every maximal outerplanar graph G of order n at least that does not belong to has a dominating set D of order at most such that every component of the subgraph of G induced by D has order at least k.     

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.     

Thoroughly dispersed colorings

We consider (not necessarily proper) colorings of the vertices of a graph where every color is thoroughly dispersed, that is, appears in every open neighborhood. Equivalently, every color is a total dominating set. We define as the maximum number of colors in such a coloring and as the fractional version thereof. In particular, we show that every claw‐free graph with minimum degree at least  two has  and this is best possible. For planar graphs, we show that every triangular disc has and this is best possible, and that every planar graph has and this is best possible, while we conjecture that every planar triangulation has . Further, although there are arbitrarily large examples of connected, cubic graphs with , we show that for a connected cubic graph . We also consider the related concepts in hypergraphs.