*n*is sufficiently large, then

*H*is Hamiltonian.

Let *p* be a prime greater than 5. We show that, while the generalized Petersen graphs of the form have cellular toroidal embeddings, they have no such embeddings having the additional property that a free action of a group on the graph extends to a cellular automorphism of the torus. Such an embedding is called a derived embedding. We also show that does have a derived embedding in the torus, and we show that for any odd *q*, each generalized Petersen graph of the form has a derived embedding in the Klein bottle, which has the same Euler characteristic as the torus. We close with some comments that frame these results in the light of Abrams and Slilaty's recent work on graphs featuring group actions that extend to spherical embeddings of those graphs.

In the paper Combinatorica 33(2) (2013) 231–252, Huggett and Moffatt characterized all bipartite partial duals of a plane graph in terms of oriented circuits in its medial graph. An open problem posed in their paper is the characterization of Eulerian partial duals of plane graphs. In this article, we solve this problem by considering half-edge orientations of medial graphs.

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 .

We show that posets of bounded height whose cover graphs exclude a fixed graph as a topological minor have bounded dimension. This result was already proven by Walczak. However, our argument is entirely combinatorial and does not rely on structural decomposition theorems. Given a poset with large dimension but bounded height, we directly find a large clique subdivision in its cover graph. Therefore, our proof is accessible to readers not familiar with topological graph theory, and it allows us to provide explicit upper bounds on the dimension. With the introduced tools we show a second result that is supporting a conjectured generalization of the previous result. We prove that -free posets whose cover graphs exclude a fixed graph as a topological minor contain only standard examples of size bounded in terms of *k*.

We initiate a general study of what we call orientation completion problems. For a fixed class of oriented graphs, the orientation completion problem asks whether a given partially oriented graph *P* can be completed to an oriented graph in by orienting the (nonoriented) edges in *P*. Orientation completion problems commonly generalize several existing problems including recognition of certain classes of graphs and digraphs as well as extending representations of certain geometrically representable graphs.

We study orientation completion problems for various classes of oriented graphs, including *k*-arc-strong oriented graphs, *k*-strong oriented graphs, quasi-transitive-oriented graphs, local tournaments, acyclic local tournaments, locally transitive tournaments, locally transitive local tournaments, in-tournaments, and oriented graphs that have directed cycle factors. We show that the orientation completion problem for each of these classes is either polynomial time solvable or NP-complete. We also show that some of the NP-complete problems become polynomial time solvable when the input-oriented graphs satisfy certain extra conditions. Our results imply that the representation extension problems for proper interval graphs and for proper circular arc graphs are polynomial time solvable. The latter generalizes a previous result.

A *Grünbaum coloring* of a triangulation *G* is a map *c* : such that for each face *f* of *G*, the three edges of the boundary walk of *f* are colored by three distinct colors. By Four Color Theorem, it is known that every triangulation on the sphere has a Grünbaum coloring. So, in this article, we investigate the question whether each even (i.e., Eulerian) triangulation on a surface with representativity at least *r* has a Grünbaum coloring. We prove that, regardless of the representativity, every even triangulation on a surface has a Grünbaum coloring as long as is the projective plane, the torus, or the Klein bottle, and we observe that the same holds for any surface with sufficiently large representativity. On the other hand, we construct even triangulations with no Grünbaum coloring and representativity , and 3 for all but finitely many surfaces. In dual terms, our results imply that no snark admits an even map on the projective plane, the torus, or the Klein bottle, and that all but finitely many surfaces admit an even map of a snark with representativity at least 3.

In this article, we consider the following problem proposed by Locke and Zhang in 1991: Let *G* be a *k*-connected graph with minimum degree *d* and *X* a set of *m* vertices on a cycle of *G*. For which values of *m* and *k*, with , must *G* have a cycle of length at least passing through *X*? Fujisawa and Yamashita solved this problem for the case and in 2008. We provide an affirmative answer to this problem for the case of and .

For an edge-colored graph, its minimum color degree is defined as the minimum number of colors appearing on the edges incident to a vertex and its maximum monochromatic degree is defined as the maximum number of edges incident to a vertex with a same color. A cycle is called properly colored if every two of its adjacent edges have distinct colors. In this article, we first give a minimum color degree condition for the existence of properly colored cycles, then obtain the minimum color degree condition for an edge-colored complete graph to contain properly colored triangles. Afterwards, we characterize the structure of an edge-colored complete bipartite graph without containing properly colored cycles of length 4 and give the minimum color degree and maximum monochromatic degree conditions for an edge-colored complete bipartite graph to contain properly colored cycles of length 4, and those passing through a given vertex or edge, respectively.

A hole is a chordless cycle with at least four vertices. A pan is a graph that consists of a hole and a single vertex with precisely one neighbor on the hole. An even hole is a hole with an even number of vertices. We prove that a (pan, even hole)-free graph can be decomposed by clique cutsets into essentially unit circular-arc graphs. This structure theorem is the basis of our -time certifying algorithm for recognizing (pan, even hole)-free graphs and for our -time algorithm to optimally color them. Using this structure theorem, we show that the tree-width of a (pan, even hole)-free graph is at most 1.5 times the clique number minus 1, and thus the chromatic number is at most 1.5 time the clique number.

We prove that for every graph, any vertex subset *S*, and given integers : there are *k* disjoint cycles of length at least ℓ that each contain at least one vertex from *S*, or a vertex set of size that meets all such cycles. This generalizes previous results of Fiorini and Herinckx and of Pontecorvi and Wollan.

In addition, we describe an algorithm for our main result that runs in time, where *s* denotes the cardinality of *S*.

The*r-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 .

The dichromatic number of a digraph *D* is the least number *k* such that the vertex set of *D* can be partitioned into *k* parts each of which induces an acyclic subdigraph. Introduced by Neumann-Lara in 1982, this digraph invariant shares many properties with the usual chromatic number of graphs and can be seen as the natural analog of the graph chromatic number. In this article, we study the list dichromatic number of digraphs, giving evidence that this notion generalizes the list chromatic number of graphs. We first prove that the list dichromatic number and the dichromatic number behave the same in many contexts, such as in small digraphs (by proving a directed version of Ohba's conjecture), tournaments, and random digraphs. We then consider bipartite digraphs, and show that their list dichromatic number can be as large as . We finally give a Brooks-type upper bound on the list dichromatic number of digon-free digraphs.

An odd *k*-edge-coloring of a graph *G* is a (not necessarily proper) edge-coloring with at most *k* colors such that each nonempty color class induces a graph in which every vertex is of odd degree. Pyber (1991) showed that every simple graph is odd 4-edge-colorable, and Lužar et al. (2015) showed that connected loopless graphs are odd 5-edge-colorable, with one particular exception that is odd 6-edge-colorable. In this article, we prove that connected loopless graphs are odd 4-edge-colorable, with two particular exceptions that are respectively odd 5- and odd 6-edge-colorable. Moreover, a color class can be reduced to a size at most 2.

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.

We investigate the minimum order of a linear *r*-regular *k*-uniform hypergraph, also known as an -combinatorial configuration, which contains a given linear *k*-uniform hypergraph of maximum (vertex) degree at most *r*.

We describe the missing class of the hierarchy of mixed unit interval graphs. This class is generated by the intersection graphs of families of unit intervals that are allowed to be closed, open, and left-closed-right-open. (By symmetry, considering closed, open, and right-closed-left-open unit intervals generates the same class.) We show that this class lies strictly between unit interval graphs and mixed unit interval graphs. We give a complete characterization of this new class, as well as quadratic-time algorithms that recognize graphs from this class and produce a corresponding interval representation if one exists. We also show that the algorithm from Shuchat et al. [8] directly extends to provide a quadratic-time algorithm to recognize the class of mixed unit interval graphs.

We consider an extremal problem motivated by a article of Balogh [J. Balogh, A remark on the number of edge colorings of graphs, European Journal of Combinatorics 27, 2006, 565–573], who considered edge-colorings of graphs avoiding fixed subgraphs with a prescribed coloring. More precisely, given , we look for *n*-vertex graphs that admit the maximum number of *r*-edge-colorings such that at most colors appear in edges incident with each vertex, that is, *r*-edge-colorings avoiding rainbow-colored stars with *t* edges. For large *n*, we show that, with the exception of the case , the complete graph is always the unique extremal graph. We also consider generalizations of this problem.

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.

In this article, we investigate the number of hamiltonian cycles in triangulations. We improve a lower bound of for the number of hamiltonian cycles in triangulations without separating triangles (4-connected triangulations) by Hakimi, Schmeichel, and Thomassen to a linear lower bound and show that a linear lower bound even holds in the case of triangulations with one separating triangle. We confirm their conjecture about the number of hamiltonian cycles in triangulations without separating triangles for up to 25 vertices and give computational results and constructions for triangulations with a small number of hamiltonian cycles and 1–5 separating triangles.

We study the relation between the growth rate of a graph property and the entropy of the graph limits that arise from graphs with that property. In particular, for hereditary classes we obtain a new description of the coloring number, which by well-known results describes the rate of growth. We study also random graphs and their entropies. We show, for example, that if a hereditary property has a unique limiting graphon with maximal entropy, then a random graph with this property, selected uniformly at random from all such graphs with a given order, converges to this maximizing graphon as the order tends to infinity.

We solve the following problem: Can an undirected weighted graph *G* be partitioned into two nonempty induced subgraphs satisfying minimum constraints for the sum of edge weights at vertices of each subgraph? We show that this is possible for all constraints satisfying , for every vertex *x*, where are, respectively, the sum and maximum of incident edge weights.

Thomassen proved that every planar graph *G* on *n* vertices has at least distinct *L*-colorings if *L* is a 5-list-assignment for *G* and at least distinct *L*-colorings if *L* is a 3-list-assignment for *G* and *G* has girth at least five. Postle and Thomas proved that if *G* is a graph on *n* vertices embedded on a surface Σ of genus *g*, then there exist constants such that if *G* has an *L*-coloring, then *G* has at least distinct *L*-colorings if *L* is a 5-list-assignment for *G* or if *L* is a 3-list-assignment for *G* and *G* has girth at least five. More generally, they proved that there exist constants such that if *G* is a graph on *n* vertices embedded in a surface Σ of fixed genus *g*, *H* is a proper subgraph of *G*, and ϕ is an *L*-coloring of *H* that extends to an *L*-coloring of *G*, then ϕ extends to at least distinct *L*-colorings of *G* if *L* is a 5-list-assignment or if *L* is a 3-list-assignment and *G* has girth at least five. We prove the same result if *G* is triangle-free and *L* is a 4-list-assignment of *G*, where , and .

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 .

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

The Wonderful Lemma, that was first proved by Roussel and Rubio, is one of the most important tools in the proof of the Strong Perfect Graph Theorem. Here we give a short proof of this lemma.

Brualdi and Hollingsworth conjectured that, for even *n*, in a proper edge coloring of using precisely colors, the edge set can be partitioned into spanning trees which are rainbow (and hence, precisely one edge from each color class is in each spanning tree). They proved that there always are two edge disjoint rainbow spanning trees. Krussel, Marshall, and Verrall improved this to three edge disjoint rainbow spanning trees. Recently, Carraher, Hartke and the author proved a theorem improving this to rainbow spanning trees, even when more general edge colorings of are considered. In this article, we show that if is properly edge colored with colors, a positive fraction of the edges can be covered by edge disjoint rainbow spanning trees.

In a recent seminal work, Kostochka and Yancey proved that for every 4-critical graph *G*. In this article, we prove that for every 4-critical graph *G* with girth at least five. When combined with another result of the second author, the improvement on the constant term leads to a corollary that there exist such that for every 4-critical graph *G* with girth at least five. Moreover, it provides a unified and shorter proof of both a result of Thomassen and a result of Thomas and Walls without invoking any topological property, where the former proves that every graph with girth five embeddable in the projective plane or torus is 3-colorable, and the latter proves the same for the Klein bottle.

We describe an algorithm for generating all *k*-critical -free graphs, based on a method of Hoàng et al. (A graph *G* is *k**-critical* *H**-free* if *G* is *H*-free, *k*-chromatic, and every *H*-free proper subgraph of *G* is -colorable). Using this algorithm, we prove that there are only finitely many 4-critical -free graphs, for both and . We also show that there are only finitely many 4-critical -free graphs. For each of these cases we also give the complete lists of critical graphs and vertex-critical graphs. These results generalize previous work by Hell and Huang, and yield certifying algorithms for the 3-colorability problem in the respective classes. In addition, we prove a number of characterizations for 4-critical *H*-free graphs when *H* is disconnected. Moreover, we prove that for every *t*, the class of 4-critical planar -free graphs is finite. We also determine all 52 4-critical planar *P*_{7}-free graphs. We also prove that every *P*_{11}-free graph of girth at least five is 3-colorable, and show that this is best possible by determining the smallest 4-chromatic *P*_{12}-free graph of girth at least five. Moreover, we show that every *P*_{14}-free graph of girth at least six and every *P*_{17}-free graph of girth at least seven is 3-colorable. This strengthens results of Golovach et al.

We construct a family of countexamples to a conjecture of Galvin [5], which stated that for any *n*-vertex, *d*-regular graph *G* and any graph *H* (possibly with loops),

where is the number of homomorphisms from *G* to *H*. By exploiting properties of the graph tensor product and graph exponentiation, we also find new infinite families of *H* for which the bound stated above on holds for all *n*-vertex, *d*-regular *G*. In particular, we show that if *H*_{WR} is the complete looped path on three vertices, also known as the Widom–Rowlinson graph, then

for all *n*-vertex, *d*-regular *G*. This verifies a conjecture of Galvin.

Aigner and Fromme initiated the systematic study of the *cop number* of a graph by proving the elegant and sharp result that in every connected planar graph, three cops are sufficient to win a natural pursuit game against a single robber. This game, introduced by Nowakowski and Winkler, is commonly known as *Cops and Robbers* in the combinatorial literature. We extend this study to directed planar graphs, and establish separation from the undirected setting. We exhibit a geometric construction that shows that a sophisticated robber strategy can indefinitely evade three cops on a particular strongly connected planar-directed graph.

We take an application of the Kernel Lemma by Kostochka and Yancey [11] to its logical conclusion. The consequence is a sort of magical way to draw conclusions about list coloring (and online list coloring) just from the existence of an independent set incident to many edges. We use this to prove an Ore-degree version of Brooks' Theorem for online list-coloring. The Ore-degree of an edge in a graph *G* is . The Ore-degree of *G* is . We show that every graph with and is online -choosable. In addition, we prove an upper bound for online list-coloring triangle-free graphs: . Finally, we characterize Gallai trees as the connected graphs *G* with no independent set incident to at least edges.

We show that the edges of every 3-connected planar graph except *K*_{4} can be colored with two colors in such a way that the graph has no color-preserving automorphisms. Also, we characterize all graphs that have the property that their edges can be 2-colored so that no matter how the graph is embedded in any orientable surface, there is no homeomorphism of the surface that induces a nontrivial color-preserving automorphism of the graph.

Let ( be two positive integers. We generalize the well-studied notions of -colorings and of the circular chromatic number to signed graphs. This implies a new notion of colorings of signed graphs, and the corresponding chromatic number χ. Some basic facts on circular colorings of signed graphs and on the circular chromatic number are proved, and differences to the results on unsigned graphs are analyzed. In particular, we show that the difference between the circular chromatic number and the chromatic number of a signed graph is at most 1. Indeed, there are signed graphs where the difference is 1. On the other hand, for a signed graph on *n* vertices, if the difference is smaller than 1, then there exists , such that the difference is at most .

We also show that the notion of -colorings is equivalent to *r*-colorings (see [12] (X. Zhu, Recent developments in circular coloring of graphs, in Topics in Discrete Mathematics Algorithms and Combinatorics Volume **26**, Springer Berlin Heidelberg, 2006, pp. 497–550)).

We find a formula for the number of directed 5-cycles in a tournament in terms of its edge scores and use the formula to find upper and lower bounds on the number of 5-cycles in any *n*-tournament. In particular, we show that the maximum number of 5-cycles is asymptotically equal to , the expected number 5-cycles in a random tournament (), with equality (up to order of magnitude) for almost all tournaments.

Let be the largest integer such that, for all graphs *G* on *n* vertices, the edge set can be partitioned into at most parts, of which every part either is a single edge or forms a graph isomorphic to *H*. Pikhurko and Sousa conjectured that for and all sufficiently large *n*, where denotes the maximum number of edges of graphs on *n* vertices that do not contain *H* as a subgraph. A -fan is a graph on vertices consisting of *k* cliques of order *r* that intersect in exactly one common vertex. In this article, we verify Pikhurko and Sousa's conjecture for -fans. The result also generalizes a result of Liu and Sousa.

In this article, we will first find the path convex Ramsey numbers for two-colorings. Then using this, we will deduce some bounds for path convex Ramsey numbers for multicolorings. Next, we will find the convex Ramsey numbers for convex paths versus any graph containing a convex cycle, for convex paths versus stars, and for convex cycles versus stars.

Given a graph *H*, a graph *G* is called a *Ramsey graph of* *H* if there is a monochromatic copy of *H* in every coloring of the edges of *G* with two colors. Two graphs *G*, *H* are called *Ramsey equivalent* if they have the same set of Ramsey graphs. Fox et al. (J Combin Theory Ser B 109 (2014), 120–133) asked whether there are two nonisomorphic connected graphs that are Ramsey equivalent. They proved that a clique is not Ramsey equivalent to any other connected graph. Results of Nešetřil et al. showed that any two graphs with different clique number (Combinatorica 1(2) (1981), 199–202) or different odd girth (Comment Math Univ Carolin 20(3) (1979), 565–582) are not Ramsey equivalent. These are the only structural graph parameters we know that “distinguish” two graphs in the above sense. This article provides further supportive evidence for a negative answer to the question of Fox et al. by claiming that for wide classes of graphs, the chromatic number is a distinguishing parameter. In addition, it is shown here that all stars and paths and all connected graphs on at most five vertices are not Ramsey equivalent to any other connected graph. Moreover, two connected graphs are not Ramsey equivalent if they belong to a special class of trees or to classes of graphs with clique-reduction properties.

A well-known combinatorial theorem says that a set of *n* non-collinear points in the plane determines at least *n* distinct lines. Chen and Chvátal conjectured that this theorem extends to metric spaces, with an appropriated definition of line. In this work, we prove a slightly stronger version of Chen and Chvátal conjecture for a family of graphs containing chordal graphs and distance-hereditary graphs.

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 .

Inspired by a 1987 result of Hanson and Toft [Edge-colored saturated graphs, J Graph Theory 11 (1987), 191–196] and several recent results, we consider the following saturation problem for edge-colored graphs. An edge-coloring of a graph *F* is *rainbow* if every edge of *F* receives a different color. Let denote the set of rainbow-colored copies of *F*. A *t*-edge-colored graph *G* is *-saturated* if *G* does not contain a rainbow copy of *F* but for any edge and any color , the addition of *e* to *G* in color *i* creates a rainbow copy of *F*. Let denote the minimum number of edges in an -saturated graph of order *n*. We call this the *rainbow saturation number* of *F*. In this article, we prove several results about rainbow saturation numbers of graphs. In stark contrast with the related problem for monochromatic subgraphs, wherein the saturation is always linear in *n*, we prove that rainbow saturation numbers have a variety of different orders of growth. For instance, the rainbow saturation number of the complete graph lies between and , the rainbow saturation number of an *n*-vertex star is quadratic in *n*, and the rainbow saturation number of any tree that is not a star is at most linear.

We show that a tree of order *n* has at most nonisomorphic subtrees, and that this bound is best possible. We also prove an analogous result for the number of nonisomorphic rooted subtrees of a rooted tree.

Frame matroids and lifted-graphic matroids are two interesting generalizations of graphic matroids. Here, we introduce a new generalization, *quasi-graphic matroids*, that unifies these two existing classes. Unlike frame matroids and lifted-graphic matroids, it is easy to certify that a matroid is quasi-graphic. The main result of the article is that every 3-connected representable quasi-graphic matroid is either a lifted-graphic matroid or a frame matroid.

A graph is called equimatchable if all of its maximal matchings have the same size. Kawarabayashi, Plummer, and Saito showed that the only connected equimatchable 3-regular graphs are *K*_{4} and *K*_{3, 3}. We extend this result by showing that for an odd positive integer *r*, if *G* is a connected equimatchable *r*-regular graph, then . Also it is proved that for an even *r*, a connected triangle-free equimatchable *r*-regular graph is isomorphic to one of the graphs *C*_{5}, *C*_{7}, and .

Fox–Grinshpun–Pach showed that every 3-coloring of the complete graph on *n* vertices without a rainbow triangle contains a clique of size that uses at most two colors, and this bound is tight up to the constant factor. We show that if instead of looking for large cliques one only tries to find subgraphs of large chromatic number, one can do much better. We show that every such coloring contains a 2-colored subgraph with chromatic number at least , and this is best possible. We further show that for fixed positive integers with , every *r*-coloring of the edges of the complete graph on *n* vertices without a rainbow triangle contains a subgraph that uses at most *s* colors and has chromatic number at least , and this is best possible. Fox–Grinshpun–Pach previously showed a clique version of this result. As a direct corollary of our result we obtain a generalization of the celebrated theorem of Erdős-Szekeres, which states that any sequence of *n* numbers contains a monotone subsequence of length at least . We prove that if an *r*-coloring of the edges of an *n*-vertex tournament does not contain a rainbow triangle then there is an *s*-colored directed path on vertices, which is best possible. This gives a partial answer to a question of Loh.

We prove that there is no polynomial with the property that a matroid *M* can be determined to be either a lifted-graphic or frame matroid using at most rank evaluations. This resolves two conjectures of Geelen, Gerards, and Whittle (Quasi-graphic matroids, to appear in J. Graph Theory).

Let *G* be an *n*-vertex simple graph, and let and denote the maximum degree and chromatic index of *G*, respectively. Vizing proved that or . Define *G* to be Δ-critical if and for every proper subgraph *H* of *G*. In 1965, Vizing conjectured that if *G* is an *n*-vertex Δ-critical graph, then *G* has a 2-factor. Luo and Zhao showed if *G* is an *n*-vertex Δ-critical graph with , then *G* has a hamiltonian cycle, and so *G* has a 2-factor. In this article, we show that if *G* is an *n*-vertex Δ-critical graph with , then *G* has a 2-factor.

We call a graph *G* a *platypus* if *G* is non-hamiltonian, and for any vertex *v* in *G*, the graph is traceable. Every hypohamiltonian and every hypotraceable graph is a platypus, but there exist platypuses that are neither hypohamiltonian nor hypotraceable. Among other things, we give a sharp lower bound on the size of a platypus depending on its order, draw connections to other families of graphs, and solve two open problems of Wiener. We also prove that there exists a *k*-connected platypus for every .

We study conjectures relating degree conditions in 3-partite hypergraphs to the matching number of the hypergraph, and use topological methods to prove special cases. In particular, we prove a strong version of a theorem of Drisko [14] (as generalized by the first two authors [2]), that every family of matchings of size *n* in a bipartite graph has a partial rainbow matching of size *n*. We show that milder restrictions on the sizes of the matchings suffice. Another result that is strengthened is a theorem of Cameron and Wanless [11], that every Latin square has a generalized diagonal (set of *n* entries, each in a different row and column) in which no symbol appears more than twice. We show that the same is true under the weaker condition that the square is row-Latin.

A *k*-*weak bisection* of a cubic graph *G* is a partition of the vertex-set of *G* into two parts *V*_{1} and *V*_{2} of equal size, such that each connected component of the subgraph of *G* induced by () is a tree of at most vertices. This notion can be viewed as a relaxed version of nowhere-zero flows, as it directly follows from old results of Jaeger that every cubic graph *G* with a circular nowhere-zero *r*-flow has a -*weak bisection*. In this article, we study problems related to the existence of *k*-weak bisections. We believe that every cubic graph that has a perfect matching, other than the Petersen graph, admits a 4-weak bisection and we present a family of cubic graphs with no perfect matching that do not admit such a bisection. The main result of this article is that every cubic graph admits a 5-weak bisection. When restricted to bridgeless graphs, that result would be a consequence of the assertion of the 5-flow Conjecture and as such it can be considered a (very small) step toward proving that assertion. However, the harder part of our proof focuses on graphs that do contain bridges.

A 2-cell embedding of a graph Γ into a closed (orientable or nonorientable) surface is called regular if its automorphism group acts regularly on the flags. In this article, we classify the regular embeddings of the complete multipartite graph . We show that if the number of partite sets is greater than 3, there exists no such embedding; and if the number of partite sets is 3, for any *n*, there exist one orientable regular embedding and one nonorientable regular embedding of up to isomorphism.

Partial cubes are graphs isometrically embeddable into hypercubes. In this article, it is proved that every cubic, vertex-transitive partial cube is isomorphic to one of the following graphs: , for , the generalized Petersen graph *G*(10, 3), the cubic permutahedron, the truncated cuboctahedron, or the truncated icosidodecahedron. This classification is a generalization of results of Brešar et al. (Eur J Combin 25 (2004), 55–64) on cubic mirror graphs; it includes all cubic, distance-regular partial cubes (P. M. Weichsel, Discrete Math 109 (1992), 297–306), and presents a contribution to the classification of all cubic partial cubes.

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

We describe two new algorithms for the generation of all non-isomorphic cubic graphs with girth at least that are very efficient for and show how these algorithms can be restricted to generate snarks with girth at least *k*.

Our implementation of these algorithms is more than 30, respectively 40 times faster than the previously fastest generator for cubic graphs with girth at least six and seven, respectively.

Using these generators we have also generated all nonisomorphic snarks with girth at least six up to 38 vertices and show that there are no snarks with girth at least seven up to 42 vertices. We present and analyze the new list of snarks with girth 6.

A graph is a *k*-critical graph if *G* is not -colorable but every proper subgraph of *G* is -colorable. In this article, we construct a family of 4-critical planar graphs with *n* vertices and edges. As a consequence, this improves the bound for the maximum edge density attained by Abbott and Zhou. We conjecture that this is the largest edge density for a 4-critical planar graph.

For a graph *H*, let for every edge . For and , let be a set of *k*-edge-connected *K*_{3}-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*_{3}-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.

For a graph *G* and a tree-decomposition of *G*, the *chromatic number* of is the maximum of , taken over all bags . The *tree-chromatic number* of *G* is the minimum chromatic number of all tree-decompositions of *G*. The *path-chromatic number* of *G* is defined analogously. In this article, we introduce an operation that always increases the path-chromatic number of a graph. As an easy corollary of our construction, we obtain an infinite family of graphs whose path-chromatic number and tree-chromatic number are different. This settles a question of Seymour (J Combin Theory Ser B 116 (2016), 229–237). Our results also imply that the path-chromatic numbers of the Mycielski graphs are unbounded.

A *diamond* is a graph on vertices with exactly one pair of nonadjacent vertices, and an *odd hole* is an induced cycle of odd length greater than 3. If *G* and *H* are graphs, *G* is *H-free* if no induced subgraph of *G* is isomorphic to *H*. A *clique-coloring* of *G* is an assignment of colors to the vertices of *G* such that no inclusion-wise maximal clique of size at least 2 is monochromatic. We show that every (diamond, odd-hole)-free graph is 3-clique-colorable, answering a question of Bacsó et al. (SIAM J Discrete Math 17(3) (2004), 361–376).

A graph is *H*-free if it has no induced subgraph isomorphic to *H*. Brandstädt, Engelfriet, Le, and Lozin proved that the class of chordal graphs with independence number at most 3 has unbounded clique-width. Brandstädt, Le, and Mosca erroneously claimed that the gem and co-gem are the only two 1-vertex *P*_{4}-extensions *H* for which the class of *H*-free chordal graphs has bounded clique-width. In fact we prove that bull-free chordal and co-chair-free chordal graphs have clique-width at most 3 and 4, respectively. In particular, we find four new classes of *H*-free chordal graphs of bounded clique-width. Our main result, obtained by combining new and known results, provides a classification of all but two stubborn cases, that is, with two potential exceptions we determine *all* graphs *H* for which the class of *H*-free chordal graphs has bounded clique-width. We illustrate the usefulness of this classification for classifying other types of graph classes by proving that the class of -free graphs has bounded clique-width via a reduction to *K*_{4}-free chordal graphs. Finally, we give a complete classification of the (un)boundedness of clique-width of *H*-free weakly chordal graphs.

A noncomplete graph Γ is said to be (*G*, 2)-distance transitive if *G* is a subgroup of the automorphism group of Γ that is transitive on the vertex set of Γ, and for any vertex *u* of Γ, the stabilizer is transitive on the sets of vertices at distances 1 and 2 from *u*. This article investigates the family of (*G*, 2)-distance transitive graphs that are not (*G*, 2)-arc transitive. Our main result is the classification of such graphs of valency not greater than 5. We also prove several results about (*G*, 2)-distance transitive, but not (*G*, 2)-arc transitive graphs of girth 4.

The authors previously published an iterative process to generate a class of projective-planar *K*_{3, 4}-free graphs called “patch graphs.” They also showed that any simple, almost 4-connected, nonplanar, and projective-planar graph that is *K*_{3, 4}-free is a subgraph of a patch graph. In this article, we describe a simpler and more natural class of cubic *K*_{3, 4}-free projective-planar graphs that we call *Möbius hyperladders*. Furthermore, every simple, almost 4-connected, nonplanar, and projective-planar graph that is *K*_{3, 4}-free is a minor of a Möbius hyperladder. As applications of these structures we determine the page number of patch graphs and of Möbius hyperladders.

The size-Ramsey number of a graph *G* is the minimum number of edges in a graph *H* such that every 2-edge-coloring of *H* yields a monochromatic copy of *G*. Size-Ramsey numbers of graphs have been studied for almost 40 years with particular focus on the case of trees and bounded degree graphs.

We initiate the study of size-Ramsey numbers for *k*-uniform hypergraphs. Analogous to the graph case, we consider the size-Ramsey number of cliques, paths, trees, and bounded degree hypergraphs. Our results suggest that size-Ramsey numbers for hypergraphs are extremely difficult to determine, and many open problems remain.

We consider graphs *G* with such that and for every edge *e*, so-called *critical* graphs. Jakobsen noted that the Petersen graph with a vertex deleted, , is such a graph and has average degree only . He showed that every critical graph has average degree at least , and asked if is the only graph where equality holds. A result of Cariolaro and Cariolaro shows that this is true. We strengthen this average degree bound further. Our main result is that if *G* is a subcubic critical graph other than , then *G* has average degree at least . This bound is best possible, as shown by the Hajós join of two copies of .