A graph is said to be -, where is the minor relation between graphs, if whenever is a graph with for all , then one also has , where is the disjoint union of many copies of . A well-known conjecture of Andreae is that every locally finite connected graph is -ubiquitous. In this paper we give a sufficient condition on the structure of the ends of a graph which implies that is -ubiquitous. In particular this implies that the full-grid is -ubiquitous.

Goodman proved that the sum of the number of triangles in a graph on nodes and its complement is at least ; in other words, this sum is minimized, asymptotically, by a random graph with edge density 1/2. Erdős conjectured that a similar inequality will hold for in place of , but this was disproved by Thomason. But an analogous statement does hold for some other graphs, which are called . Characterization of common graphs seems, however, out of reach. Franek and Rödl proved that is common in a weaker, local sense. Using the language of graph limits, we study two versions of locally common graphs. We sharpen a result of Jagger, Štovíček and Thomason by showing that no graph containing can be locally common, but prove that all such graphs are weakly locally common. We also show that not all connected graphs are weakly locally common.

A well-known conjecture of Alspach says that every -regular Cayley graph of a finite abelian group can be decomposed into Hamiltonian cycles. We consider an analogous question for infinite abelian groups. In this setting one natural analogue of a Hamiltonian cycle is a spanning double-ray. However, a naive generalisation of Alspach's conjecture fails to hold in this setting due to the existence of -regular Cayley graphs with finite cuts , where and differ in parity, which necessarily preclude the existence of a decomposition into spanning double-rays. We show that every 4-regular Cayley graph of an infinite abelian group all of whose finite cuts are even can be decomposed into spanning double-rays, and so characterise when such decompositions exist. We also characterise when such graphs can be decomposed either into Hamiltonian circles, a more topological generalisation of a Hamiltonian cycle in infinite graphs, or into a Hamiltonian circle and a spanning double-ray.

Given , there exists such that, if , then for any graph on vertices of maximum degree in which the neighbourhood of every vertex in spans at most edges, (i)an independent set of drawn uniformly at random has at least vertices in expectation, and(ii)the fractional chromatic number of is at most . These bounds cannot in general be improved by more than a factor 2 asymptotically. One may view these as stronger versions of results of Ajtai, Komlós and Szemerédi and Shearer. The proofs use a tight analysis of the hard-core model.

Given a multigraph, suppose that each vertex is given a local assignment of colours to its incident edges. We are interested in whether there is a choice of one local colour per vertex such that no edge has both of its local colours chosen. The least for which this is always possible given any set of local assignments we call the of the graph. This parameter is closely related to separation choosability and adaptable choosability. We show that single-conflict chromatic number of simple graphs embeddable on a surface of Euler genus is as . This is sharp up to the logarithmic factor.

We study the existence of hamiltonian cycles in plane cubic graphs having a facial 2-factor . Thus hamiltonicity in is transformed into the existence of a (quasi) spanning tree of faces in the contraction . In particular, we study the case where is the leapfrog extension (called vertex envelope of a plane cubic graph . As a consequence we prove hamiltonicity in the leapfrog extension of planar cubic cyclically 4-edge-connected bipartite graphs. This and other results of this paper establish partial solutions of Barnette's Conjecture according to which every 3-connected cubic planar bipartite graph is hamiltonian. These results go considerably beyond Goodey's result on this topic.

Let be a multigraph with for each vertex a cyclic order of the edges incident with it. For , let be the dihedral group of order . Define . Goodall et al in 2016 asked whether admits a nowhere-identity -flow if and only if it admits a nowhere-identity -flow with (a "nowhere-identity dihedral -flow"). We give counterexamples to this statement and provide general obstructions. Furthermore, the complexity of deciding the existence of nowhere-identity -flows is discussed. Lastly, graphs in which the equivalence of the existence of flows as above is true are described. We focus particularly on cubic graphs.

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

Let be a graph whose edges are colored with colors, and H=(H1,⋯,Hk) be a -tuple of graphs. A H- of is a partition of the edge set of such that each part is either a single edge or forms a monochromatic copy of Hi in color , for some 1≤i≤k. Let φk(n,H) be the smallest number ϕ, such that, for every order- graph and every -edge-coloring, there is a monochromatic H-decomposition with at most ϕ elements. Extending the previous results of Liu and Sousa [Monochromatic Kr-decompositions of graphs, 76 (2014), 89-100], we solve this problem when each graph in H is a clique and n≥n0(H) is sufficiently large.