The structure of (theta,pyramid, 1-wheel, 3-wheel)-free graphs

In this paper, we study the class of graphs defined by excluding the following structures as induced subgraphs: theta, pyramid, 1-wheel, and 3-wheel. We describe the structure of graphs in , and we give a polynomial-time recognition algorithm for this class. We also prove that -free graphs in are 4-colorable. We remark that includes the class of chordal graphs, as well as the class of line graphs of triangle-free graphs.     

Nonrepetitive colorings of graphs excluding a fixed immersion or topological minor

We prove that graphs excluding a fixed immersion have bounded nonrepetitive chromatic number. More generally, we prove that if is a fixed planar graph that has a planar embedding with all the vertices with degree at least 4 on a single face, then graphs excluding as a topological minor have bounded nonrepetitive chromatic number. This is the largest class of graphs known to have bounded nonrepetitive chromatic number.     

Colourings of cubic graphs inducing isomorphic monochromatic subgraphs

A -bisection of a bridgeless cubic graph is a -colouring of its vertex set such that the colour classes have the same cardinality and all connected components in the two subgraphs induced by the colour classes ( monochromatic components in what follows) have order at most . Ban and Linial Conjectured that every bridgeless cubic graph admits a -bisection except for the Petersen graph. A similar problem for the edge set of cubic graphs has been studied: Wormald conjectured that every cubic graph with has a -edge colouring such that the two monochromatic subgraphs are isomorphic linear forests (ie, a forest whose components are paths). Finally, Ando conjectured that every cubic graph admits a bisection such that the two induced monochromatic subgraphs are isomorphic. In this paper, we provide evidence of a strong relation of the conjectures of Ban-Linial and Wormald with Ando's Conjecture. Furthermore, we also give computational and theoretical evidence in their support. As a result, we pose some open problems stronger than the above-mentioned conjectures. Moreover, we prove Ban-Linial's Conjecture for cubic-cycle permutation graphs. As a by-product of studying -edge colourings of cubic graphs having linear forests as monochromatic components, we also give a negative answer to a problem posed by Jackson and Wormald about certain decompositions of cubic graphs into linear forests.     

Hamiltonicity of planar graphs with a forbidden minor

Tutte showed that -connected planar graphs are Hamiltonian, but it is well known that -connected planar graphs need not be Hamiltonian. We show that -minor-free -connected planar graphs are Hamiltonian. This does not extend to -minor-free -connected graphs in general, as shown by the Petersen graph, and does not extend to -minor-free -connected planar graphs, as we show by an infinite family of examples.     

On the local density problem for graphs of given odd-girth

Erdős conjectured that every n-vertex triangle-free graph contains a subset of vertices that spans at most edges. Extending a recent result of Norin and Yepremyan, we confirm this conjecture for graphs homomorphic to so-called Andrásfai graphs. As a consequence, Erdős' conjecture holds for every triangle-free graph G with minimum degree and if the degree condition can be relaxed to . In fact, we obtain a more general result for graphs of higher odd-girth.     

Pairs and triples of forbidden subgraphs and the existence of a 2-factor

Let be a set of connected graphs, each of which has order at least three, and suppose that there exist infinitely many connected -free graphs of minimum degree at least  two and all except for finitely many of them have a 2-factor. In [J. Graph Theory, 64 (2010), 250–266], we proved that if , then one of the members in is a star. In this article, we determine the remaining members of and hence give a complete characterization of the pairs and triples of forbidden subgraphs.     

Shorter signed circuit covers of graphs

A signed circuit is a minimal signed graph (with respect to inclusion) that admits a nowhere-zero flow. We show that each flow-admissible signed graph on edges can be covered by signed circuits of total length at most , improving a recent result of Cheng et al. To obtain this improvement, we prove several results on signed circuit covers of trees of Eulerian graphs, which are connected signed graphs such that removing all bridges results in a collection of Eulerian graphs.     

Triangle-free planar graphs with the smallest independence number

Steinberg and Tovey proved that every -vertex planar triangle-free graph has an independent set of size at least , and described an infinite class of tight examples. We show that all -vertex planar triangle-free graphs except for this one infinite class have independent sets of size at least .     

On the independence number of graphs related to a polarity

We investigate the independence number of two graphs constructed from a polarity of . For the first graph under consideration, the Erdős-Rényi graph , we provide an improvement on the known lower bounds on its independence number. In the second part of the paper, we consider the Erdős-Rényi hypergraph of triangles . We determine the exact magnitude of the independence number of , even. This solves a problem posed by Mubayi and Williford [On the independence number of the ErdŐs-RÉnyi and projective norm graphs and a related hypergraph, J. Graph Theory, 56 (2007), pp. 113-127, Open Problem 3].     

Complete graphs with no rainbow tree

We study colorings of the edges of the complete graph . For some graph , we say that a coloring contains a rainbow , if there is an embedding of into , such that all edges of the embedded copy have pairwise distinct colors. The main emphasis of this paper is a classification of those forbidden rainbow graphs that force a low number of vertices of a high color degree, along with some specifications and more general information in certain cases. Those graphs turn out to be of two special types of trees of small diameter.     

Rainbow triangles and the Caccetta-Häggkvist conjecture

A famous conjecture of Caccetta and Häggkvist is that in a digraph on vertices and minimum outdegree at least n/r there is a directed cycle of length or less. We consider the following generalization: in an undirected graph on vertices, any collection of disjoint sets of edges, each of size at least n/r, has a rainbow cycle of length or less. We focus on the case and prove the existence of a rainbow triangle under somewhat stronger conditions than in the conjecture. In our main result, whenever is larger than a suitable polynomial in , we determine the maximum number of edges in an -vertex edge-colored graph where all color classes have size at most and there is no rainbow triangle. Moreover, we characterize the extremal graphs for this problem.     

The edge-subgraph poset of a graph and the edge reconstruction conjecture

We consider only finite simple graphs in this paper. Earlier we showed that many invariants of a graph can be computed from the isomorphism class of its partially ordered set of distinct unlabeled non-empty induced subgraphs, that is, the subgraphs themselves are not required. In this paper, we consider an analogous problem of reconstructing an arbitrary graph up to isomorphism from its abstract edge-subgraph poset , which we call the -reconstruction problem. We present an infinite family of graphs that are not -reconstructible and show that the edge reconstruction conjecture is true if and only if the graphs in the family are the only graphs that are not -reconstructible. Let be the set of all unlabeled graphs. Let denote the number of homomorphisms from to . Let be a bijection such that for all , we have . We conjecture that is the identity map. Our conjecture is motivated by the homomorphism cancellation results of Lovász. We prove that the conjecture stated above is weaker than the edge reconstruction conjecture.     

Arc index of spatial graphs

Bae and Park found an upper bound on the arc index of prime links in terms of the minimal crossing number. In this paper, we extend the definition of the arc presentation to spatial graphs and find an upper bound on the arc index of any spatial graph as where is the minimal crossing number of , is the number of edges, and is the number of bouquet cut-components. This upper bound is lowest possible.     

Partitioning a graph into monochromatic connected subgraphs

We show that every -edge-colored graph on vertices with minimum degree at least can be partitioned into two monochromatic connected subgraphs, provided is sufficiently large. This minimum degree condition is tight and the result proves a conjecture of Bal and DeBiasio. We also make progress on another conjecture of Bal and DeBiasio on covering graphs with large minimum degree with monochromatic components of distinct colors.     

Bounded diameter arboricity

We introduce the notion of bounded diameter arboricity. Specifically, the diameter- arboricity of a graph is the minimum number such that the edges of the graph can be partitioned into forests each of whose components has diameter at most . A class of graphs has bounded diameter arboricity if there exists a natural number such that every graph in the class has diameter- arboricity at most . We conjecture that the class of graphs with arboricity at most has bounded diameter arboricity at most . We prove this conjecture for by proving the stronger assertion that the union of a forest and a star forest can be partitioned into two forests of diameter at most 18. We use these results to characterize the bounded diameter arboricity for planar graphs of girth at least for all . As an application we show that every 6-edge-connected planar (multi)graph contains two edge-disjoint -thin spanning trees. Moreover, we answer a question by Mütze and Peter, leading to an improved lower bound on the density of globally sparse Ramsey graphs.     

On dihedral flows in embedded graphs

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.     

A note on immersion intertwines of infinite graphs

We present a construction of two infinite graphs and , and of an infinite set of graphs such that is an antichain with respect to the immersion relation and, for each graph in , both and are subgraphs of , but no graph properly immersed in admits an immersion of and of . This shows that the class of infinite graphs ordered by the immersion relation does not have the finite intertwine property.     

The 1-2-3-conjecture holds for dense graphs

This paper confirms the 1-2-3-conjecture for graphs that can be edge-decomposed into cliques of order at least 3. Furthermore we combine this with a result by Barber, Kühn, Lo, and Osthus to show that there is a constants such that every graph with and , where is the minimum degree of satisfying the 1-2-3-conjecture.     

Edge clique cover of claw-free graphs

The smallest number of cliques, covering all edges of a graph , is called the (edge) clique cover number of and is denoted by . It is an easy observation that if is a line graph on vertices, then . G. Chen et al. [Discrete Math. 219 (2000), no. 1–3, 17–26; MR1761707] extended this observation to all quasi-line graphs and questioned if the same assertion holds for all claw-free graphs. In this paper, using the celebrated structure theorem of claw-free graphs due to Chudnovsky and Seymour, we give an affirmative answer to this question for all claw-free graphs with independence number at least three. In particular, we prove that if is a connected claw-free graph on vertices with three pairwise nonadjacent vertices, then and the equality holds if and only if is either the graph of icosahedron, or the complement of a graph on vertices called “twister” or the power of the cycle , for some positive integer .