Hamilton Cycles,Minimum Degree,and Bipartite Holes

We present a tight extremal threshold for the existence of Hamilton cycles in graphs with large minimum degree and without a large “bipartite hole” (two disjoint sets of vertices with no edges between them). This result extends Dirac's classical theorem, and is related to a theorem of Chvátal and Erd?s. In detail, an ‐bipartite‐hole in a graph G consists of two disjoint sets of vertices S and T with and such that there are no edges between S and T ; and is the maximum integer r such that G contains an ‐bipartite‐hole for every pair of nonnegative integers s and t with . Our central theorem is that a graph G with at least three vertices is Hamiltonian if its minimum degree is at least . From the proof we obtain a polynomial time algorithm that either finds a Hamilton cycle or a large bipartite hole. The theorem also yields a condition for the existence of k edge‐disjoint Hamilton cycles. We see that for dense random graphs , the probability of failing to contain many edge‐disjoint Hamilton cycles is . Finally, we discuss the complexity of calculating and approximating .     

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 .     

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 .     

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.     

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.     

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.     

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.     

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 .     

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

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 .     

Decomposition of complete uniform multi‐hypergraphs into Berge paths and cycles

In 2015, Bryant, Horsley, Maenhaut, and Smith, generalizing a well‐known conjecture by Alspach, obtained the necessary and sufficient conditions for the decomposition of the complete multigraph into cycles of arbitrary lengths, where I is empty, when is even and I is a perfect matching, when is odd. Moreover, Bryant in 2010, verifying a conjecture by Tarsi, proved that the obvious necessary conditions for packing pairwise edge‐disjoint paths of arbitrary lengths in are also sufficient. In this article, first, we obtain the necessary and sufficient conditions for packing edge‐disjoint cycles of arbitrary lengths in . Then, applying this result, we investigate the analogous problem of the decomposition of the complete uniform multihypergraph into Berge cycles and paths of arbitrary given lengths. In particular, we show that for every integer , and , can be decomposed into Berge cycles and paths of arbitrary lengths, provided that the obvious necessary conditions hold, thereby generalizing a result by Kühn and Osthus on the decomposition of into Hamilton Berge cycles.     

Some results on cyclic interval edge colorings of graphs

A proper edge coloring of a graph G with colors is called a cyclic interval t‐coloring if for each vertex v of G the edges incident to v are colored by consecutive colors, under the condition that color 1 is considered as consecutive to color t. We prove that a bipartite graph G of even maximum degree admits a cyclic interval ‐coloring if for every vertex v the degree satisfies either or . We also prove that every Eulerian bipartite graph G with maximum degree at most eight has a cyclic interval coloring. Some results are obtained for ‐biregular graphs, that is, bipartite graphs with the vertices in one part all having degree a and the vertices in the other part all having degree b; it has been conjectured that all these have cyclic interval colorings. We show that all (4, 7)‐biregular graphs as well as all ‐biregular () graphs have cyclic interval colorings. Finally, we prove that all complete multipartite graphs admit cyclic interval colorings; this proves a conjecture of Petrosyan and Mkhitaryan.     

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 .     

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 a Problem of Judicious k‐Partitions of Graphs

For positive integers and m , let be the smallest integer such that for each graph G with m edges there exists a k‐partition in which each contains at most edges. Bollobás and Scott showed that . Ma and Yu posed the following problem: is it true that the limsup of tends to infinity as m tends to infinity? They showed it holds when k is even, establishing a conjecture of Bollobás and Scott. In this article, we solve the problem completely. We also present a result by showing that every graph with a large k‐cut has a k‐partition in which each vertex class contains relatively few edges, which partly improves a result given by Bollobás and Scott.     

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.     

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

Plane Graphs with Maximum Degree Are Entirely ‐Colorable

Let be a plane graph with the sets of vertices, edges, and faces V, E, and F, respectively. If one can color all elements in using k colors so that any two adjacent or incident elements receive distinct colors, then G is said to be entirely k‐colorable. Kronk and Mitchem [Discrete Math 5 (1973) 253‐260] conjectured that every plane graph with maximum degree Δ is entirely ‐colorable. This conjecture has now been settled in Wang and Zhu (J Combin Theory Ser B 101 (2011) 490–501), where the authors asked: is every simple plane graph entirely ‐colorable? In this article, we prove that every simple plane graph with is entirely ‐colorable, and conjecture that every simple plane graph, except the tetrahedron, is entirely ‐colorable.     

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.     

Cycles with two blocks in k‐chromatic digraphs

Let k and ℓ be positive integers. A cycle with two blocks is a digraph obtained by an orientation of an undirected cycle, which consists of two internally (vertex) disjoint paths of lengths at least k and ℓ, respectively, from a vertex to another one. A problem of Addario‐Berry, Havet and Thomassé [J. Combin. Theory Ser. B 97 (2007), 620–626] asked if, given positive integers k and ℓ such that , any strongly connected digraph D containing no has chromatic number at most . In this article, we show that such digraph D has chromatic number at most , improving the previous upper bound of Cohen et al. [Subdivisions of oriented cycles in digraphs with large chromatic number, to appear]. We also show that if in addition D is Hamiltonian, then its underlying simple graph is ‐degenerate and thus the chromatic number of D is at most , which is tight.