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

Let be a graph of density *p* on *n* vertices. Following Erdős, Łuczak, and Spencer, an *m*-vertex subgraph *H* of *G* is called *full* if *H* has minimum degree at least . Let denote the order of a largest full subgraph of *G*. If is a nonnegative integer, define

Erdős, Łuczak, and Spencer proved that for ,

In this article, we prove the following lower bound: for ,

Furthermore, we show that this is tight up to a multiplicative constant factor for infinitely many *p* near the elements of . In contrast, we show that for any *n*-vertex graph *G*, either *G* or contains a full subgraph on vertices. Finally, we discuss full subgraphs of random and pseudo-random graphs, and several open problems.

Chudnovsky, Kim, Oum, and Seymour recently established that any prime graph contains one of a short list of induced prime subgraphs [1]. In the present article, we reprove their theorem using many of the same ideas, but with the key model-theoretic ingredient of first determining the so-called amount of stability of the graph. This approach changes the applicable Ramsey theorem, improves the bounds and offers a different structural perspective on the graphs in question. Complementing this, we give an infinitary proof that implies the finite result.

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

A path cover of a graph is a set of disjoint paths so that every vertex in the graph is contained in one of the paths. The path cover number of graph *G* is the cardinality of a path cover with the minimum number of paths. Reed in 1996 conjectured that a 2-connected 3-regular graph has path cover number at most . In this article, we confirm this conjecture.

For a maximal outerplanar graph *G* of order *n* at least three, Matheson and Tarjan showed that *G* has domination number at most . Similarly, for a maximal outerplanar graph *G* of order *n* at least five, Dorfling, Hattingh, and Jonck showed, by a completely different approach, that *G* has total domination number at most unless *G* is isomorphic to one of two exceptional graphs of order 12.

We present a unified proof of a common generalization of these two results. For every positive integer *k*, we specify a set of graphs of order at least and at most such that every maximal outerplanar graph *G* of order *n* at least that does not belong to has a dominating set *D* of order at most such that every component of the subgraph of *G* induced by *D* has order at least *k*.

In this work, we present a generalization of Gale's lemma. Using this generalization, we introduce two sharp combinatorial lower bounds for and , the two classic topological lower bounds for the chromatic number of a graph *G*.

We improve by an exponential factor the lower bound of Körner and Muzi for the cardinality of the largest family of Hamilton paths in a complete graph of *n* vertices in which the union of any two paths has maximum degree 4. The improvement is through an explicit construction while the previous bound was obtained by a greedy algorithm. We solve a similar problem for permutations up to an exponential factor.

The entropy of a digraph is a fundamental measure that relates network coding, information theory, and fixed points of finite dynamical systems. In this article, we focus on the entropy of undirected graphs. We prove any bounded interval only contains finitely many possible values of the entropy of an undirected graph. We also determine all the possible values for the entropy of an undirected graph up to the value of four.

Let be *k* nonnegative integers. A graph *G* is -colorable if the vertex set can be partitioned into *k* sets , such that the subgraph , induced by , has maximum degree at most for . Let denote the family of plane graphs with neither adjacent 3-cycles nor 5-cycles. Borodin and Raspaud (2003) conjectured that each graph in is (0, 0, 0)-colorable (which was disproved very recently). In this article, we prove that each graph in is (1, 1, 0)-colorable, which improves the results by Xu (2009) and Liu-Li-Yu (2016).

A well-known theorem of Gomory and Hu states that if *G* is a finite graph with nonnegative weights on its edges, then there exists a tree *T* (now called a Gomory-Hu tree) on such that for all there is an such that the two components of determine an optimal (minimal valued) cut between *u* an *v* in *G*. In this article, we extend their result to infinite weighted graphs with finite total weight. Furthermore, we show by an example that one cannot omit the condition of the finiteness of the total weight.

Suppose is a loopless graph and is the graph obtained from *G* by subdividing each of its edges *k* () times. Let be the set of all spanning trees of *G*, be the line graph of the graph and be the number of spanning trees of . By using techniques from electrical networks, we first obtain the following simple formula:

Then we find it is in fact equivalent to a complicated formula obtained recently using combinatorial techniques in [F. M. Dong and W. G. Yan, Expression for the number of spanning trees of line graphs of arbitrary connected graphs, J. Graph Theory. 85 (2017) 74–93].

Let *G* be a finite group and a class function. Let be a directed graph with for each vertex a cyclic order of the edges incident to it. The cyclic orders give a collection *F* of faces of *H*. Define the partition function , where denotes the product of the κ-values of the edges incident with *v* (in cyclic order), where the inverse is taken for edges leaving *v*. Write , where the sum runs over irreducible representations λ of *G* with character and with for every λ. When *H* is connected, it is proved that , where 1 is the identity element of *G*. Among the corollaries, a formula for the number of nowhere-identity *G*-flows on *H* is derived, generalizing a result of Tutte. We show that these flows correspond bijectively to certain proper *G*-colorings of a covering graph of the dual graph of *H*. This correspondence generalizes coloring-flow duality for planar graphs.

A tournament is called locally transitive if the outneighborhood and the inneighborhood of every vertex are transitive. Equivalently, a tournament is locally transitive if it avoids the tournaments *W*_{4} and *L*_{4}, which are the only tournaments up to isomorphism on four vertices containing a unique 3-cycle. On the other hand, a sequence of tournaments with is called almost balanced if all but vertices of have outdegree . In the same spirit of quasi-random properties, we present several characterizations of tournament sequences that are both almost balanced and asymptotically locally transitive in the sense that the density of *W*_{4} and *L*_{4} in goes to zero as *n* goes to infinity.

An *immersion* of a graph *H* in another graph *G* is a one-to-one mapping and a collection of edge-disjoint paths in *G*, one for each edge of *H*, such that the path corresponding to the edge has endpoints and . The immersion is *strong* if the paths are internally disjoint from . We prove that every simple graph of minimum degree at least contains a strong immersion of the complete graph . This improves on previously known bound of minimum degree at least 200*t* obtained by DeVos et al. Our result supports a conjecture of Lescure and Meyniel (also independently proposed by Abu-Khzam and Langston), which is the analogue of famous Hadwiger’s conjecture for immersions and says that every graph without a -immersion is -colorable.

A graph is 1-planar if it can be drawn in the plane such that each edge is crossed at most once. A graph, together with a 1-planar drawing is called 1-plane. A graph is maximal 1-planar (1-plane), if we cannot add any missing edge so that the resulting graph is still 1-planar (1-plane). Brandenburg et al. showed that there are maximal 1-planar graphs with only edges and maximal 1-plane graphs with only edges. On the other hand, they showed that a maximal 1-planar graph has at least edges, and a maximal 1-plane graph has at least edges. We improve both lower bounds to .

For minimally *k*-connected graphs on *n* vertices, Mader proved a tight lower bound for the number of vertices of degree *k* in dependence on *n* and *k*. Oxley observed 1981 that in many cases a considerably better bound can be given if is used as additional parameter, i.e. in dependence on *m*, *n*, and *k*. It was left open to determine whether Oxley's more general bound is best possible. We show that this is not the case, but give a closely related bound that deviates from a variant of Oxley's long-standing one only for small values of *m*. We prove that this new bound is best possible. The bound contains Mader's bound as special case.

There are three main thrusts to this article: a new proof of Levi's Enlargement Lemma for pseudoline arrangements in the real projective plane; a new characterization of pseudolinear drawings of the complete graph; and proofs that pseudolinear and convex drawings of have O and O(*n*^{2}), respectively, empty triangles. All the arguments are elementary, algorithmic, and self-contained.

Weconsider the largest number of minimal separators a graph on *n* vertices can have.

- –We give a new proof that this number is in .
- –We prove that this number is in , improving on the previous best lower bound of .

This gives also an improved lower bound on the number of potential maximal cliques in a graph. We would like to emphasize that our proofs are short, simple, and elementary.

For a sequence *d* of nonnegative integers, let and be the sets of all graphs and forests with degree sequence *d*, respectively. Let , , , and where is the domination number and is the independence number of a graph *G*. Adapting results of Havel and Hakimi, Rao showed in 1979 that can be determined in polynomial time. We establish the existence of realizations with , and with and that have strong structural properties. This leads to an efficient algorithm to determine for every given degree sequence *d* with bounded entries as well as closed formulas for and .

In 1994, J. Chen, J. Gross, and R. Rieper demonstrated how to use the rank of Mohar's overlap matrix to calculate the crosscap-number distribution, that is, the distribution of the embeddings of a graph in the nonorientable surfaces. That has ever since been by far the most frequent way that these distributions have been calculated. This article introduces a way to calculate the *Euler-genus polynomial* of a graph, which combines the orientable and the nonorientable embeddings, without using the overlap matrix. The crosscap-number polynomial for the nonorientable embeddings is then easily calculated from the Euler-genus polynomial and the genus polynomial.

It is conjectured by Berge and Fulkerson that *every bridgeless cubic graph has six perfect matchings such that each edge is contained in exactly two of them*.
Let *G* be a cubic graph and be a 2-factor of *G* such that is odd if and only if for some integer *k*. The 2-factor *F* is *C*_{(8)}*-linked*
if, for every , there is a circuit of length 8 with edge sequence where and . And the cubic graph *G* is *C*_{(8)}-linked if it contains a *C*_{(8)}-linked 2-factor. It is proved in this article that *every* *C*_{(8)}*-linked cubic graph is Berge–Fulkerson colorable*.
It is also noticed that many classical families of snarks (including some high oddness snarks) are *C*_{(8)}-linked. Consequently, the Berge–Fulkerson conjecture is verified for these infinite families of snarks.

We prove that every 3-connected 2-indivisible infinite planar graph has a 1-way infinite 2-walk. (A graph is *2-indivisible* if deleting finitely many vertices leaves at most one infinite component, and a *2-walk* is a spanning walk using every vertex at most twice.) This improves a result of Timar, which assumed local finiteness. Our proofs use Tutte subgraphs, and allow us to also provide other results when the graph is bipartite or an infinite analog of a triangulation: then the prism over the graph has a spanning 1-way infinite path.

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 3-connected matroid is quasi-graphic. The main result is that every 3-connected representable quasi-graphic matroid is either a lifted-graphic matroid or a frame matroid.

Take a graph *G*, an edge subset , and a set of terminals where is even. The triple is called a *signed graft*. A *T*-join is *odd* if it contains an odd number of edges from Σ. Let ν be the maximum number of edge-disjoint odd *T*-joins. A *signature* is a set of the form where and is even. Let τ be the minimum cardinality a *T*-cut or a signature can achieve. Then and we say that *packs* if equality holds here.

We prove that packs if the signed graft is Eulerian and it excludes two special nonpacking minors. Our result confirms the Cycling Conjecture for the class of clutters of odd *T*-joins with at most two terminals. Corollaries of this result include, the characterizations of weakly and evenly bipartite graphs, packing two-commodity paths, packing *T*-joins with at most four terminals, and a new result on covering edges with cuts.

This article focuses on the problem of determining the mean orders of sub-*k*-trees of *k*-trees. It is shown that the problem of finding the mean order of all sub-*k*-trees containing a given *k*-clique *C*, can be reduced to the previously studied problem of finding the mean order of subtrees of a tree that contain a given vertex. This problem is extended in two ways. The first of these extensions focuses on the mean order of sub-*k*-trees containing a given sub-*k*-tree. The second extension focuses on the expected number of *r*-cliques, , in a randomly chosen sub-*k*-tree containing a fixed sub-*k*-tree *X*. Sharp lower bounds for both invariants are derived. The article concludes with a study of global mean orders of sub-*k*-trees of a *k*-tree. For a *k*-tree, from the class of simple-clique *k*-trees, it is shown that the mean order of its sub-*k*-trees is asymptotically equal to the mean subtree order of its dual. For general *k*-trees a recursive generating function for the number of sub-*k*-trees of a given *k*-tree *T* is derived.

An induced matching *M* in a graph *G* is dominating if every edge not in *M* shares exactly one vertex with an edge in *M*. The dominating induced matching problem (also known as efficient edge domination) asks whether a graph *G* contains a dominating induced matching. This problem is generally NP-complete, but polynomial-time solvable for graphs with some special properties. In particular, it is solvable in polynomial time for claw-free graphs. In the present article, we provide a polynomial-time algorithm to solve the dominating induced matching problem for graphs containing no long claw, that is, no induced subgraph obtained from the claw by subdividing each of its edges exactly once.

A graph *G* is *hypohamiltonian* if *G* is non-hamiltonian and for every vertex *v* in *G*, the graph is hamiltonian. McKay asked in [*J. Graph Theory* 85 (2017) 7–11] whether infinitely many planar cubic hypohamiltonian graphs of girth 5 exist. We settle this question affirmatively.

Jones, Nedela, and Škoviera (2008) showed that a complete bipartite graph has a unique orientably regular embedding if and only if . In this article, we extend this result by proving that a complete bipartite graph has a unique orientably edge-transitive embedding if and only if .

The problem of when a given digraph contains a subdivision of a fixed digraph *F* is considered. Bang-Jensen et al. [4] laid out foundations for approaching this problem from the algorithmic point of view. In this article, we give further support to several open conjectures and speculations about algorithmic complexity of finding *F*-subdivisions. In particular, up to five exceptions, we completely classify for which 4-vertex digraphs *F*, the *F*-subdivision problem is polynomial-time solvable and for which it is NP-complete. While all NP-hardness proofs are made by reduction from some version of the 2-linkage problem in digraphs, some of the polynomial-time solvable cases involve relatively complicated algorithms.

In this article, we show that every bridgeless graph *G* of order *n* and maximum degree Δ has an orientation of diameter at most . We then use this result and the definition , for every subgraph *H* of *G*, to give better bounds in the case that *G* contains certain clusters of high-degree vertices, namely: For every edge *e*, *G* has an orientation of diameter at most , if *e* is on a triangle and at most , otherwise. Furthermore, for every bridgeless subgraph *H* of *G*, there is such an orientation of diameter at most . Finally, if *G* is bipartite, then we show the existence of an orientation of diameter at most , for every partite set *A* of *G* and . This particularly implies that balanced bipartite graphs have an orientation of diameter at most . For each bound, we give a polynomial-time algorithm to construct a corresponding orientation and an infinite family of graphs for which the bound is sharp.

If *G* is a graph and is a set of subgraphs of *G*, then an edge-coloring of *G* is called -polychromatic if every graph from gets all colors present in *G*. The -polychromatic number of *G*, denoted , is the largest number of colors such that *G* has an -polychromatic coloring. In this article, is determined exactly when *G* is a complete graph and is the family of all 1-factors. In addition is found up to an additive constant term when *G* is a complete graph and is the family of all 2-factors, or the family of all Hamiltonian cycles.

A caterpillar is a tree having a path that contains all vertices of of degree at least 3. We show in this article that every balanced caterpillar with maximum degree 3 and 2^{n} vertices is a subgraph of the *n*-dimensional hypercube. This solves a long-standing open problem and generalizes a result of Havel and Liebl (1986), who considered only such caterpillars that have a path containing all vertices of degree at least 2.

A graph *G* is hypohamiltonian/hypotraceable if it is not hamiltonian/traceable, but all vertex-deleted subgraphs of *G* are hamiltonian/traceable. All known hypotraceable graphs are constructed using hypohamiltonian graphs; here we present a construction that uses so-called almost hypohamiltonian graphs (nonhamiltonian graphs, whose vertex-deleted subgraphs are hamiltonian with exactly one exception, see [15]). This construction is an extension of a method of Thomassen [11]. As an application, we construct a planar hypotraceable graph of order 138, improving the best-known bound of 154 [8]. We also prove a structural type theorem showing that hypotraceable graphs possessing some connectivity properties are all built using either Thomassen's or our method. We also prove that if *G* is a Grinbergian graph without a triangular region, then *G* is not maximal nonhamiltonian and using the proof method we construct a hypohamiltonian graph of order 36 with crossing number 1, improving the best-known bound of 46 [14].

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

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.

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.

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.

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

The above article, published online on 8 March 2017 in Wiley Online Library (www.onlinelibrary.wiley.com), has been retracted at the request of the authors. The retraction is made due to an error in Lemma 3.5, which results in errors in all of the major results reported in the paper. These issues are resolved in a corrected version of the paper [J. Geelen, B. Gerards, G. Whittle. *Quasi-graphic matroids*. J. Graph Theory 00 (2017), 1–12. https://doi.org/10.1002/jgt.22177]

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.

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

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 .

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.

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.

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

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

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 .

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.