A spanning tree without a vertex of degree two is called a HIST, which is an abbreviation for homeomorphically irreducible spanning tree. We provide a necessary condition for the existence of a HIST in a cubic graph. As one consequence, we answer affirmatively an open question on HISTs by Albertson, Berman, Hutchinson, and Thomassen. We also show several results on the existence of HISTs in plane and toroidal cubic graphs.

Let be integers with , and set . Erdős proved that when , each *n*-vertex nonhamiltonian graph *G* with minimum degree has at most edges. He also provides a sharpness example for all such pairs . Previously, we showed a stability version of this result: for *n* large enough, every nonhamiltonian graph *G* on *n* vertices with and more than edges is a subgraph of . In this article, we show that not only does the graph maximize the number of edges among nonhamiltonian graphs with *n* vertices and minimum degree at least *d*, but in fact it maximizes the number of copies of any fixed graph *F* when *n* is sufficiently large in comparison with *d* and . We also show a stronger stability theorem, that is, we classify all nonhamiltonian *n*-vertex graphs with and more than edges. We show this by proving a more general theorem: we describe all such graphs with more than copies of for any *k*.

An edge in a *k*-connected graph *G* is called *k**-contractible* if the graph obtained from *G* by contracting *e* is *k*-connected. Generalizing earlier results on 3-contractible edges in spanning trees of 3-connected graphs, we prove that (except for the graphs if ) (a) every spanning tree of a *k*-connected triangle free graph has two *k*-contractible edges, (b) every spanning tree of a *k*-connected graph of minimum degree at least has two *k*-contractible edges, (c) for , every DFS tree of a *k*-connected graph of minimum degree at least has two *k*-contractible edges, (d) every spanning tree of a cubic 3-connected graph nonisomorphic to *K*_{4} has at least many 3-contractible edges, and (e) every DFS tree of a 3-connected graph nonisomorphic to *K*_{4}, the prism, or the prism plus a single edge has two 3-contractible edges. We also discuss in which sense these theorems are best possible.

A simple graph is a (2, 1)-circuit if and for every proper subgraph *H* of *G*. Motivated, in part, by ongoing work to understand unique realisations of graphs on surfaces, we derive a constructive characterisation of (2, 1)-circuits. The characterisation uses the well-known 1-extension and *X*-replacement operations as well as several summation moves to glue together (2, 1)-circuits over small cutsets.

Let . We prove the following three bounds for the matching number, , of a graph, *G*, of order *n* size *m* and maximum degree at most *k*.

- If
*k*is odd, then . - If
*k*is even, then . - If
*k*is even, then .

In this article, we actually prove a slight strengthening of the above for which the bounds are tight for essentially all densities of graphs.

The above three bounds are in fact powerful enough to give a complete description of the set of pairs of real numbers with the following property. There exists a constant *K* such that for every connected graph *G* with maximum degree at most *k*, where *n* and *m* denote the number of vertices and the number of edges, respectively, in *G*. We show that is a convex set. Further, if *k* is odd, then is the intersection of two closed half-spaces, and there is exactly one extreme point of , while if *k* is even, then is the intersection of three closed half-spaces, and there are precisely two extreme points of .

The Turán number of a graph *H*, , is the maximum number of edges in any graph of order *n* that does not contain an *H* as a subgraph. A graph on vertices consisting of *k* triangles that intersect in exactly one common vertex is called a *k*-fan, and a graph consisting of *k* cycles that intersect in exactly one common vertex is called a *k*-flower. In this article, we determine the Turán number of any *k*-flower containing at least one odd cycle and characterize all extremal graphs provided *n* is sufficiently large. Erdős, Füredi, Gould, and Gunderson determined the Turán number for the *k*-fan. Our result is a generalization of their result. The addition aim of this article is to draw attention to a powerful tool, the so-called progressive induction lemma of Simonovits.

A digraph *D* is supereulerian if *D* has a spanning closed ditrail. Bang-Jensen and Thomassé conjectured that if the arc-strong connectivity of a digraph *D* is not less than the independence number , then *D* is supereulerian. A digraph is bipartite if its underlying graph is bipartite. Let be the size of a maximum matching of *D*. We prove that if *D* is a bipartite digraph satisfying , then *D* is supereulerian. Consequently, every bipartite digraph *D* satisfying is supereulerian. The bound of our main result is best possible.

We show that every 4-chromatic graph on *n* vertices, with no two vertex-disjoint odd cycles, has an odd cycle of length at most . Let *G* be a nonbipartite quadrangulation of the projective plane on *n* vertices. Our result immediately implies that *G* has edge-width at most , which is sharp for infinitely many values of *n*. We also show that *G* has face-width (equivalently, contains an odd cycle transversal of cardinality) at most , which is a constant away from the optimal; we prove a lower bound of . Finally, we show that *G* has an odd cycle transversal of size at most inducing a single edge, where Δ is the maximum degree. This last result partially answers a question of Nakamoto and Ozeki.

We improve the upper bound on the Ramsey number *R*(5, 5) from to . We also complete the catalog of extremal graphs for *R*(4, 5).

A matching *M* in a graph *G* is uniquely restricted if there is no matching in *G* that is distinct from *M* but covers the same vertices as *M*. Solving a problem posed by Golumbic, Hirst, and Lewenstein, we characterize the graphs in which some maximum matching is uniquely restricted. Solving a problem posed by Levit and Mandrescu, we characterize the graphs in which every maximum matching is uniquely restricted. Both our characterizations lead to efficient recognition algorithms for the corresponding graphs.

The *separation dimension* of a hypergraph *G* is the smallest natural number *k* for which the vertices of *G* can be embedded in so that any pair of disjoint edges in *G* can be separated by a hyperplane normal to one of the axes. Equivalently, it is the cardinality of a smallest family of total orders of , such that for any two disjoint edges of *G*, there exists at least one total order in in which all the vertices in one edge precede those in the other. Separation dimension is a monotone parameter; adding more edges cannot reduce the separation dimension of a hypergraph. In this article, we discuss the influence of separation dimension and edge-density of a graph on one another. On one hand, we show that the maximum separation dimension of a *k*-degenerate graph on *n* vertices is and that there exists a family of 2-degenerate graphs with separation dimension . On the other hand, we show that graphs with bounded separation dimension cannot be very dense. Quantitatively, we prove that *n*-vertex graphs with separation dimension *s* have at most edges. We do not believe that this bound is optimal and give a question and a remark on the optimal bound.

A signed graph, denoted by , is a graph *G* associated with a mapping . A *cycle* of is a connected 2-regular subgraph. A cycle *C* is *positive* if it has an even number of negative edges, and negative otherwise. A *signed-circuit* of a signed graph is a positive cycle or a barbell consisting of two edge-disjoint negative cycles joined by a path. The definition of a signed-circuit of signed graph comes from the signed-graphic matroid. A signed-circuit cover of is a family of signed-circuits covering all edges of . A signed-circuit cover with the smallest total length is called a shortest signed-circuit cover of and its length is denoted by . Bouchet proved that a signed graph has a signed-circuit cover if and only if it is flow-admissible (i.e., has a nowhere-zero integer flow). In this article, we show that a 3-connected flow-admissible signed graph does not necessarily have a signed-circuit double cover. For shortest signed-circuit cover of 2-edge-connected cubic signed graphs , we show that if it is flow-admissible.

The 3-Decomposition Conjecture states that every connected cubic graph can be decomposed into a spanning tree, a 2-regular subgraph and a matching. We show that this conjecture holds for the class of connected plane cubic graphs.

Motivated by an old conjecture of P. Erdős and V. Neumann-Lara, our aim is to investigate digraphs with uncountable dichromatic number and orientations of undirected graphs with uncountable chromatic number. A graph has uncountable *chromatic number* if its vertices cannot be covered by countably many independent sets, and a digraph has uncountable *dichromatic number* if its vertices cannot be covered by countably many acyclic sets. We prove that, consistently, there are digraphs with uncountable dichromatic number and arbitrarily large digirth; this is in surprising contrast with the undirected case: any graph with uncountable chromatic number contains a 4-cycle. Next, we prove that several well-known graphs (uncountable complete graphs, certain comparability graphs, and shift graphs) admit orientations with uncountable dichromatic number in ZFC. However, we show that the statement “every graph *G* of size and chromatic number ω_{1} has an orientation *D* with uncountable dichromatic number” is independent of ZFC. We end the article with several open problems.

The natural infinite analog of a (finite) Hamilton cycle is a two-way-infinite Hamilton path (connected spanning 2-valent subgraph). Although it is known that every connected 2*k*-valent infinite circulant graph has a two-way-infinite Hamilton path, there exist many such graphs that do not have a decomposition into *k* edge-disjoint two-way-infinite Hamilton paths. This contrasts with the finite case where it is conjectured that every 2*k*-valent connected circulant graph has a decomposition into *k* edge-disjoint Hamilton cycles. We settle the problem of decomposing 2*k*-valent infinite circulant graphs into *k* edge-disjoint two-way-infinite Hamilton paths for , in many cases when , and in many other cases including where the connection set is or .

*Correspondence coloring*, or *DP-coloring*, is a generalization of list coloring introduced recently by Dvořák and Postle [11]. In this article, we establish a version of Dirac's theorem on the minimum number of edges in critical graphs [9] in the framework of DP-colorings. A corollary of our main result answers a question posed by Kostochka and Stiebitz [15] on classifying list-critical graphs that satisfy Dirac's bound with equality.

Given a zero-sum function with , an orientation *D* of *G* with in for every vertex is called a β-orientation. A graph *G* is -connected if *G* admits a β-orientation for every zero-sum function β. Jaeger et al. conjectured that every 5-edge-connected graph is -connected. A graph is -extendable at vertex *v* if any preorientation at *v* can be extended to a β-orientation of *G* for any zero-sum function β. We observe that if every 5-edge-connected essentially 6-edge-connected graph is -extendable at any degree five vertex, then the above-mentioned conjecture by Jaeger et al. holds as well. Furthermore, applying the partial flow extension method of Thomassen and of Lovász et al., we prove that every graph with at least four edge-disjoint spanning trees is -connected. Consequently, every 5-edge-connected essentially 23-edge-connected graph is -extendable at any degree five vertex.

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

We prove the titular statement. This settles a problem of Chvátal from 1973 and encompasses earlier results of Thomassen, who showed it for *K*_{3}, and Collier and Schmeichel, who proved it for bipartite graphs. We also show that for every outerplanar graph there exists a planar hypohamiltonian graph containing it as an induced subgraph.

We study feedback vertex sets (FVS) in tournaments, which are orientations of complete graphs. As our main result, we show that any tournament on *n* nodes has at most 1.5949^{n} minimal FVS. This significantly improves the previously best upper bound of 1.6667^{n} by Fomin et al. [STOC 2016] and 1.6740^{n} by Gaspers and Mnich [*J. Graph Theory* **72**(1):72–89, 2013]. Our new upper bound almost matches the best-known lower bound of , due to Gaspers and Mnich. Our proof is algorithmic, and shows that all minimal FVS of tournaments can be enumerated in time .

The *star chromatic index* of a multigraph *G*, denoted , is the minimum number of colors needed to properly color the edges of *G* such that no path or cycle of length four is bicolored. A multigraph *G* is *star* *k**-edge-colorable* if . Dvořák, Mohar, and Šámal [Star chromatic index, *J. Graph Theory* **72** (2013), 313–326] proved that every subcubic multigraph is star 7-edge-colorable. They conjectured in the same article that every subcubic multigraph should be star 6-edge-colorable. In this article, we first prove that it is NP-complete to determine whether for an arbitrary graph *G*. This answers a question of Mohar. We then establish some structure results on subcubic multigraphs *G* with such that but for any , where . We finally apply the structure results, along with a simple discharging method, to prove that every subcubic multigraph *G* is star 6-edge-colorable if , and star 5-edge-colorable if , respectively, where is the maximum average degree of a multigraph *G*. This partially confirms the conjecture of Dvořák, Mohar, and Šámal.

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

We show that the class of multigraphs with at most *p* connected components and bonds of size at most *k* is well-quasi-ordered by edge contraction for all positive integers . (A *bond* is a minimal nonempty edge cut.) We also characterize canonical antichains for this relation.

The clique chromatic number of a graph is the minimum number of colors in a vertex coloring so that no maximal (with respect to containment) clique is monochromatic. We prove that the clique chromatic number of the binomial random graph is, with high probability, . This settles a problem of McDiarmid, Mitsche, and Prałat who proved that it is with high probability.

A 2-matching of a graph *G* is a spanning subgraph with maximum degree two. The size of a 2-matching *U* is the number of edges in *U* and this is at least where *n* is the number of vertices of *G* and κ denotes the number of components. In this article, we analyze the performance of a greedy algorithm 2greedy for finding a large 2-matching on a random 3-regular graph. We prove that with high probability, the algorithm outputs a 2-matching *U* with .

A *long unichord* in a graph is an edge that is the unique chord of some cycle of length at least 5. A graph is *long unichord free* if it does not contain any long unichord. We prove a structure theorem for long unichord free graph. We give an time algorithm to recognize them. We show that any long unichord free graph *G* can be colored with at most colors, where ω is the maximum number of pairwise adjacent vertices in *G*.

For a hypergraph *H*, let denote the minimum vertex degree in *H*. Kühn, Osthus, and Treglown proved that, for any sufficiently large integer *n* with , if *H* is a 3-uniform hypergraph with order *n* and then *H* has a perfect matching, and this bound on is best possible. In this article, we show that under the same conditions, *H* contains at least pairwise disjoint perfect matchings, and this bound is sharp.

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

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.

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.

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.

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.

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.

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.

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 .

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.

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 .

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.

We study graphs where each edge that is incident to a vertex of small degree (of degree at most 7 and 9, respectively) belongs to many triangles (at least 4 and 5, respectively) and show that these graphs contain a complete graph (*K*_{6} and *K*_{7}, respectively) as a minor. The second case settles a problem of Nevo. Moreover, if each edge of a graph belongs to six triangles, then the graph contains a *K*_{8}-minor or contains *K*_{2, 2, 2, 2, 2} as an induced subgraph. We then show applications of these structural properties to stress freeness and coloring of graphs. In particular, motivated by Hadwiger's conjecture, we prove that every *K*_{7}-minor free graph is 8-colorable and every *K*_{8}-minor free graph is 10-colorable.

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

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