*n*is sufficiently large, then

*H*is Hamiltonian.

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

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 show the following for every sufficiently connected graph *G*, any vertex subset *S* of *G*, and given integer *k*: there are *k* disjoint odd cycles in *G* each containing a vertex of *S* or there is set *X* of at most vertices such that does not contain any odd cycle that contains a vertex of *S*. We prove this via an extension of Kawarabayashi and Reed's result about parity-*k*-linked graphs (Combinatorica 29, 215–225). From this result, it is easy to deduce several other well-known results about the Erdős–Pósa property of odd cycles in highly connected graphs. This strengthens results due to Thomassen (Combinatorica 21, 321–333), and Rautenbach and Reed (Combinatorica 21, 267–278), respectively.

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.

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.

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.

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.

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.

Let and . We show that, if *G* is a sufficiently large simple graph of average degree at least μ, and *H* is a random spanning subgraph of *G* formed by including each edge independently with probability , then *H* contains a cycle with probability at least .

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

Let be an integer, be the set of vertices of degree at least 2*k* 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.

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.

A graph *G* has *maximal local edge-connectivity **k* if the maximum number of edge-disjoint paths between every pair of distinct vertices *x* and *y* is at most *k*. We prove Brooks-type theorems for *k*-connected graphs with maximal local edge-connectivity *k*, and for any graph with maximal local edge-connectivity 3. We also consider several related graph classes defined by constraints on connectivity. In particular, we show that there is a polynomial-time algorithm that, given a 3-connected graph *G* with maximal local connectivity 3, outputs an optimal coloring for *G*. On the other hand, we prove, for , that *k*-colorability is NP-complete when restricted to minimally *k*-connected graphs, and 3-colorability is NP-complete when restricted to -connected graphs with maximal local connectivity *k*. Finally, we consider a parameterization of *k*-colorability based on the number of vertices of degree at least , and prove that, even when *k* is part of the input, the corresponding parameterized problem is FPT.

Our main result includes the following, slightly surprising, fact: a 4-connected nonplanar graph *G* has crossing number at least 2 if and only if, for every pair of edges having no common incident vertex, there are vertex-disjoint cycles in *G* with one containing *e* and the other containing *f*.

A weighting of the edges of a hypergraph is called vertex-coloring if the weighted degrees of the vertices yield a proper coloring of the graph, i.e. every edge contains at least two vertices with different weighted degrees. In this article, we show that such a weighting is possible from the weight set for all hypergraphs with maximum edge size and not containing edges solely consisting of identical vertices. The number is best possible for this statement.

We generalize a parity result of Fleishner and Stiebitz that being combined with Alon–Tarsi polynomial method allowed them to prove that a 4-regular graph formed by a Hamiltonian cycle and several disjoint triangles is always 3-choosable. Also we show how a version of polynomial method gives slightly more combinatorial information about colorings than direct application of Alon's Combinatorial Nullstellensatz.

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.

For graphs *G* and *H*, an *H*-coloring of *G* is a map from the vertices of *G* to the vertices of *H* that preserves edge adjacency. We consider the following extremal enumerative question: for a given *H*, which connected *n*-vertex graph with minimum degree δ maximizes the number of *H*-colorings? We show that for nonregular *H* and sufficiently large *n*, the complete bipartite graph is the unique maximizer. As a corollary, for nonregular *H* and sufficiently large *n* the graph is the unique *k*-connected graph that maximizes the number of *H*-colorings among all *k*-connected graphs. Finally, we show that this conclusion does not hold for all regular *H* by exhibiting a connected *n*-vertex graph with minimum degree δ that has more -colorings (for sufficiently large *q* and *n*) than .

A proper *k*-coloring of a graph is a function such that , for every . The chromatic number is the minimum *k* such that there exists a proper *k*-coloring of *G*. Given a spanning subgraph *H* of *G*, a *q*-backbone *k*-coloring of is a proper *k*-coloring *c* of such that , for every edge . The *q*-backbone chromatic number is the smallest *k* for which there exists a *q*-backbone *k*-coloring of . In this work, we show that every connected graph *G* has a spanning tree *T* such that , and that this value is the best possible. As a direct consequence, we get that every connected graph *G* has a spanning tree *T* for which , if , or , otherwise. Thus, by applying the Four Color Theorem, we have that every connected nonbipartite planar graph *G* has a spanning tree *T* such that . This settles a question by Wang, Bu, Montassier, and Raspaud (J Combin Optim 23(1) (2012), 79–93), and generalizes a number of previous partial results to their question.

Let *G* be a planar graph without 4-cycles and 5-cycles and with maximum degree . We prove that . For arbitrarily large maximum degree Δ, there exist planar graphs of girth 6 with . Thus, our bound is within 1 of being optimal. Further, our bound comes from coloring greedily in a good order, so the bound immediately extends to *online* list-coloring. In addition, we prove bounds for -labeling. Specifically, and, more generally, , for positive integers *p* and *q* with . Again, these bounds come from a greedy coloring, so they immediately extend to the list-coloring and online list-coloring variants of this problem.

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.

Let *c* be a proper edge coloring of a graph with integers . Then , while Vizing's theorem guarantees that we can take . On the course of investigating irregularities in graphs, it has been conjectured that with only slightly larger *k*, that is, , we could enforce an additional strong feature of *c*, namely that it attributes distinct sums of incident colors to adjacent vertices in *G* if only this graph has no isolated edges and is not isomorphic to *C*_{5}. We prove the conjecture is valid for planar graphs of sufficiently large maximum degree. In fact an even stronger statement holds, as the necessary number of colors stemming from the result of Vizing is proved to be sufficient for this family of graphs. Specifically, our main result states that every planar graph *G* of maximum degree at least 28, which contains no isolated edges admits a proper edge coloring such that for every edge of *G*.

This article introduces a new variant of hypercubes . The *n*-dimensional twisted hypercube is obtained from two copies of the -dimensional twisted hypercube by adding a perfect matching between the vertices of these two copies of . We prove that the *n*-dimensional twisted hypercube has diameter . This improves on the previous known variants of hypercube of dimension *n* and is optimal up to an error of order . Another type of hypercube variant that has similar structure and properties as is also discussed in the last section.

Recently, Borodin, Kostochka, and Yancey (Discrete Math 313(22) (2013), 2638–2649) showed that the vertices of each planar graph of girth at least 7 can be 2-colored so that each color class induces a subgraph of a matching. We prove that any planar graph of girth at least 6 admits a vertex coloring in colors such that each monochromatic component is a path of length at most 14. Moreover, we show a list version of this result. On the other hand, for each positive integer , we construct a planar graph of girth 4 such that in any coloring of vertices in colors there is a monochromatic path of length at least *t*. It remains open whether each planar graph of girth 5 admits a 2-coloring with no long monochromatic paths.

Recently, Jones et al. (Electron J Comb 22(2) (2015), #P2.53) introduced the study of *u*-representable graphs, where *u* is a word over containing at least one 1. The notion of a *u*-representable graph is a far-reaching generalization of the notion of a word-representable graph studied in the literature in a series of papers. Jones et al. have shown that any graph is 11⋅⋅⋅1-representable assuming that the number of 1s is at least three, while the class of 12-representable graphs is properly contained in the class of comparability graphs, which, in turn, is properly contained in the class of word-representable graphs corresponding to 11-representable graphs. Further studies in this direction were conducted by Nabawanda (M.Sc. thesis, 2015), who has shown, in particular, that the class of 112-representable graphs is not included in the class of word-representable graphs. Jones et al. raised a question on classification of *u*-representable graphs at least for small values of *u*. In this article, we show that if *u* is of length at least 3 then any graph is *u*-representable. This rather unexpected result shows that from existence of representation point of view there are only two interesting nonequivalent cases in the theory of *u*-representable graphs, namely, those of and .

The partition of graphs into “nice” subgraphs is a central algorithmic problem with strong ties to matching theory. We study the partitioning of undirected graphs into same-size stars, a problem known to be NP-complete even for the case of stars on three vertices. We perform a thorough computational complexity study of the problem on subclasses of perfect graphs and identify several polynomial-time solvable cases, for example, on interval graphs and bipartite permutation graphs, and also NP-complete cases, for example, on grid graphs and chordal graphs.

We give a complete description of the set of triples of real numbers with the following property. There exists a constant *K* such that is a lower bound for the matching number of every connected subcubic graph *G*, where denotes the number of vertices of degree *i* for each *i*.

For graphs *F* and *H*, we say *F* is *Ramsey for H* if every 2-coloring of the edges of *F* contains a monochromatic copy of *H*. The graph *F* is *Ramsey H*-*minimal* if *F* is Ramsey for *H* and there is no proper subgraph of *F* so that is Ramsey for *H*. Burr et al. defined to be the minimum degree of *F* over all Ramsey *H*-minimal graphs *F*. Define to be a graph on vertices consisting of a complete graph on *t* vertices and one additional vertex of degree *d*. We show that for all values ; it was previously known that , so it is surprising that is much smaller. We also make some further progress on some sparser graphs. Fox and Lin observed that for all graphs *H*, where is the minimum degree of *H*; Szabó et al. investigated which graphs have this property and conjectured that all bipartite graphs *H* without isolated vertices satisfy . Fox et al. further conjectured that all connected triangle-free graphs with at least two vertices satisfy this property. We show that *d*-regular 3-connected triangle-free graphs *H*, with one extra technical constraint, satisfy ; the extra constraint is that *H* has a vertex *v* so that if one removes *v* and its neighborhood from *H*, the remainder is connected.

Tutte's 5-flow conjecture from 1954 states that every bridgeless graph has a nowhere-zero 5-flow. It suffices to prove the conjecture for cyclically 6-edge-connected cubic graphs. We prove that every cyclically 6-edge-connected cubic graph with oddness at most 4 has a nowhere-zero 5-flow. This implies that every minimum counterexample to the 5-flow conjecture has oddness at least 6.

A spanning subgraph *F* of a graph *G* is called *perfect* if *F* is a forest, the degree of each vertex *x* in *F* is odd, and each tree of *F* is an induced subgraph of *G*. Alex Scott (Graphs Combin 17 (2001), 539–553) proved that every connected graph *G* contains a perfect forest if and only if *G* has an even number of vertices. We consider four generalizations to directed graphs of the concept of a perfect forest. While the problem of existence of the most straightforward one is NP-hard, for the three others this problem is polynomial-time solvable. Moreover, every digraph with only one strong component contains a directed forest of each of these three generalization types. One of our results extends Scott's theorem to digraphs in a nontrivial way.

We study the class of 1-perfectly orientable graphs, that is, graphs having an orientation in which every out-neighborhood induces a tournament. 1-perfectly orientable graphs form a common generalization of chordal graphs and circular arc graphs. Even though they can be recognized in polynomial time, little is known about their structure. In this article, we develop several results on 1-perfectly orientable graphs. In particular, we (i) give a characterization of 1-perfectly orientable graphs in terms of edge clique covers, (ii) identify several graph transformations preserving the class of 1-perfectly orientable graphs, (iii) exhibit an infinite family of minimal forbidden induced minors for the class of 1-perfectly orientable graphs, and (iv) characterize the class of 1-perfectly orientable graphs within the classes of cographs and of cobipartite graphs. The class of 1-perfectly orientable cobipartite graphs coincides with the class of cobipartite circular arc graphs.

Given a digraph *G*, we propose a new method to find the recurrence equation for the number of vertices of the *k*-iterated line digraph , for , where . We obtain this result by using the minimal polynomial of a quotient digraph of *G*.

Given two graphs *G* and *H*, an *H*-*decomposition* of *G* is a partition of the edge set of *G* such that each part is either a single edge or forms a graph isomorphic to *H*. Let be the smallest number ϕ such that any graph *G* of order *n* admits an *H*-decomposition with at most ϕ parts. Pikhurko and Sousa conjectured that for and all sufficiently large *n*, where denotes the maximum number of edges in a graph on *n* vertices not containing *H* as a subgraph. Their conjecture has been verified by Özkahya and Person for all edge-critical graphs *H*. In this article, the conjecture is verified for the *k*-fan graph. The *k*-*fan graph*, denoted by , is the graph on vertices consisting of *k* triangles that intersect in exactly one common vertex called the *center* of the *k*-fan.

A graph *G* is called -choosable if for any list assignment *L* that assigns to each vertex *v* a set of *a* permissible colors, there is a *b*-tuple *L*-coloring of *G*. An (*a*, 1)-choosable graph is also called *a*-choosable. In the pioneering article on list coloring of graphs by Erdős et al. , 2-choosable graphs are characterized. Confirming a special case of a conjecture in , Tuza and Voigt proved that 2-choosable graphs are -choosable for any positive integer *m*. On the other hand, Voigt proved that if *m* is an odd integer, then these are the only -choosable graphs; however, when *m* is even, there are -choosable graphs that are not 2-choosable. A graph is called 3-choosable-critical if it is not 2-choosable, but all its proper subgraphs are 2-choosable. Voigt conjectured that for every positive integer *m*, all bipartite 3-choosable-critical graphs are -choosable. In this article, we determine which 3-choosable-critical graphs are (4, 2)-choosable, refuting Voigt's conjecture in the process. Nevertheless, a weaker version of the conjecture is true: we prove that there is an even integer *k* such that for any positive integer *m*, every bipartite 3-choosable-critical graph is -choosable. Moving beyond 3-choosable-critical graphs, we present an infinite family of non-3-choosable-critical graphs that have been shown by computer analysis to be (4, 2)-choosable. This shows that the family of all (4, 2)-choosable graphs has rich structure.

We look at several saturation problems in complete balanced blow-ups of graphs. We let denote the blow-up of *H* onto parts of size *n* and refer to a copy of *H* in as *partite* if it has one vertex in each part of . We then ask how few edges a subgraph *G* of can have such that *G* has no partite copy of *H* but such that the addition of any new edge from creates a partite *H*. When *H* is a triangle this value was determined by Ferrara, Jacobson, Pfender, and Wenger in . Our main result is to calculate this value for when *n* is large. We also give exact results for paths and stars and show that for 2-connected graphs the answer is linear in *n* whilst for graphs that are not 2-connected the answer is quadratic in *n*. We also investigate a similar problem where *G* is permitted to contain partite copies of *H* but we require that the addition of any new edge from creates an extra partite copy of *H*. This problem turns out to be much simpler and we attain exact answers for all cliques and trees.

We consider random-turn positional games, introduced by Peres, Schramm, Sheffield, and Wilson in 2007. A *p*-random-turn positional game is a two-player game, played the same as an ordinary positional game, except that instead of alternating turns, a coin is being tossed before each turn to decide the identity of the next player to move (the probability of Player I to move is *p*). We analyze the random-turn version of several classical Maker–Breaker games such as the game Box (introduced by Chvátal and Erdős in 1987), the Hamilton cycle game and the *k*-vertex-connectivity game (both played on the edge set of ). For each of these games we provide each of the players with a (randomized) efficient strategy that typically ensures his win in the asymptotic order of the minimum value of *p* for which he typically wins the game, assuming optimal strategies of both players.

A graph with a trivial automorphism group is said to be *rigid*. Wright proved (Acta Math 126(1) (1971), 1–9) that for a random graph is rigid whp (with high probability). It is not hard to see that this lower bound is sharp and for with positive probability is nontrivial. We show that in the sparser case , it holds whp that *G*'s 2-core is rigid. We conclude that for all *p*, a graph in is reconstructible whp. In addition this yields for a canonical labeling algorithm that almost surely runs in polynomial time with *o*(1) error rate. This extends the range for which such an algorithm is currently known (T. Czajka and G. Pandurangan, J Discrete Algorithms 6(1) (2008), 85–92).

Given a family and a host graph *H*, a graph is -*saturated relative to H* if no subgraph of *G* lies in but adding any edge from to *G* creates such a subgraph. In the -*saturation game* on *H*, players *Max* and *Min* alternately add edges of *H* to *G*, avoiding subgraphs in , until *G* becomes -saturated relative to *H*. They aim to maximize or minimize the length of the game, respectively; denotes the length under optimal play (when Max starts).

Let denote the family of odd cycles and the family of *n*-vertex trees, and write *F* for when . Our results include , for , for , and for . We also determine ; with , it is *n* when *n* is even, *m* when *n* is odd and *m* is even, and when is odd. Finally, we prove the lower bound . The results are very similar when Min plays first, except for the *P*_{4}-saturation game on .

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.

Let *G* be a regular bipartite graph and . We show that there exist perfect matchings of *G* containing both, an odd and an even number of edges from *X* if and only if the signed graph , that is a graph *G* with exactly the edges from *X* being negative, is not equivalent to . In fact, we prove that for a given signed regular bipartite graph with minimum signature, it is possible to find perfect matchings that contain exactly no negative edges or an arbitrary one preselected negative edge. Moreover, if the underlying graph is cubic, there exists a perfect matching with exactly two preselected negative edges. As an application of our results we show that each signed regular bipartite graph that contains an unbalanced circuit has a 2-cycle-cover such that each cycle contains an odd number of negative edges.

Let and be the largest order of a Cayley graph and a Cayley graph based on an abelian group, respectively, of degree *d* and diameter *k*. When , it is well known that with equality if and only if the graph is a Moore graph. In the abelian case, we have . The best currently lower bound on is for all sufficiently large *d*. In this article, we consider the construction of large graphs of diameter 2 using generalized difference sets. We show that for sufficiently large *d* and if , and *m* is odd.

The *k*-linkage problem is as follows: given a digraph and a collection of *k* terminal pairs such that all these vertices are distinct; decide whether *D* has a collection of vertex disjoint paths such that is from to for . A digraph is *k*-linked if it has a *k*-linkage for every choice of 2*k* distinct vertices and every choice of *k* pairs as above. The *k*-linkage problem is NP-complete already for [11] and there exists no function such that every -strong digraph has a *k*-linkage for every choice of 2*k* distinct vertices of *D* [17]. Recently, Chudnovsky et al. [9] gave a polynomial algorithm for the *k*-linkage problem for any fixed *k* in (a generalization of) semicomplete multipartite digraphs. In this article, we use their result as well as the classical polynomial algorithm for the case of acyclic digraphs by Fortune et al. [11] to develop polynomial algorithms for the *k*-linkage problem in locally semicomplete digraphs and several classes of decomposable digraphs, including quasi-transitive digraphs and directed cographs. We also prove that the necessary condition of being -strong is also sufficient for round-decomposable digraphs to be *k*-linked, obtaining thus a best possible bound that improves a previous one of . Finally we settle a conjecture from [3] by proving that every 5-strong locally semicomplete digraph is 2-linked. This bound is also best possible (already for tournaments) [1].

A graph is intrinsically knotted if every embedding contains a nontrivially knotted cycle. It is known that intrinsically knotted graphs have at least 21 edges and that the KS graphs, *K*_{7} and the 13 graphs obtained from *K*_{7} by moves, are the only minor minimal intrinsically knotted graphs with 21 edges [1, 9, 11, 12]. This set includes exactly one bipartite graph, the Heawood graph. In this article we classify the intrinsically knotted bipartite graphs with at most 22 edges. Previously known examples of intrinsically knotted graphs of size 22 were those with KS graph minor and the 168 graphs in the *K*_{3, 3, 1, 1} and families. Among these, the only bipartite example with no Heawood subgraph is Cousin 110 of the family. We show that, in fact, this is a complete listing. That is, there are exactly two graphs of size at most 22 that are minor minimal bipartite intrinsically knotted: the Heawood graph and Cousin 110.

Hedetniemi conjectured in 1966 that if *G* and *H* are finite graphs with chromatic number *n*, then the chromatic number of the direct product of *G* and *H* is also *n*. We mention two well-known results pertaining to this conjecture and offer an improvement of the one, which partially proves the other. The first of these two results is due to Burr et al. (Ars Combin 1 (1976), 167–190), who showed that when every vertex of a graph *G* with is contained in an *n*-clique, then whenever . The second, by Duffus et al. (J Graph Theory 9 (1985), 487–495), and, obtained independently by Welzl (J Combin Theory Ser B 37 (1984), 235–244), states that the same is true when *G* and *H* are connected graphs each with clique number *n*. Our main result reads as follows: If *G* is a graph with and has the property that the subgraph of *G* induced by those vertices of *G* that are not contained in an *n*-clique is homomorphic to an -critical graph *H*, then . This result is an improvement of the result by the first authors. In addition we will show that our main result implies a special case of the result by the second set of authors. Our approach will employ a construction of a graph *F*, with chromatic number , that is homomorphic to *G* and *H*.