Linearly χ-bounding (P6, C4)-free graphs*

Given two graphs and , a graph is -free if it contains no induced subgraph isomorphic to or . Let and be the path on vertices and the cycle on vertices, respectively. In this paper we show that for any -free graph it holds that , where and are the chromatic number and clique number of , respectively. Our bound is attained by several graphs, for instance, the 5-cycle, the Petersen graph, the Petersen graph with an additional universal vertex, and all -critical -free graphs other than (see Hell and Huang [Discrete Appl. Math. 216 (2017), pp. 211–232]). The new result unifies previously known results on the existence of linear -binding functions for several graph classes. Our proof is based on a novel structure theorem on -free graphs that do not contain clique cutsets. Using this structure theorem we also design a polynomial time -approximation algorithm for coloring -free graphs. Our algorithm computes a coloring with colors for any -free graph in time.     

Fractal graphs

The lexicographic sum of graphs is defined as follows. Let be a graph. With each associate a graph . The lexicographic sum of the graphs over is obtained from by substituting each by . Given distinct , we have all the possible edges in the lexicographic sum between and if , and none otherwise. When all the graphs are isomorphic to some graph , the lexicographic sum of the graphs over is called the lexicographic product of by and is denoted by . We say that a graph is fractal if there exists a graph , with at least two vertices, such that . There is a simple way to construct fractal graphs. Let be a graph with at least two vertices. The graph is defined on the set of functions from to as follows. Given distinct is an edge of if is an edge of , where is the smallest integer such that . The graph is fractal because . We prove that a fractal graph is isomorphic to a lexicographic sum over an induced subgraph of , which is itself fractal.     

Filling the complexity gaps for colouring planar and bounded degree graphs

A colouring of a graph is a function such that for every . A -regular list assignment of is a function with domain such that for every , is a subset of of size . A colouring of respects a -regular list assignment of if for every . A graph is -choosable if for every -regular list assignment of , there exists a colouring of that respects . We may also ask if for a given -regular list assignment of a given graph , there exists a colouring of that respects . This yields the -Regular List Colouring problem. For , we determine a family of classes of planar graphs, such that either -Regular List Colouring is -complete for instances with , or every is -choosable. By using known examples of non--choosable and non--choosable graphs, this enables us to classify the complexity of -Regular List Colouring restricted to planar graphs, planar bipartite graphs, planar triangle-free graphs, and planar graphs with no -cycles and no -cycles. We also classify the complexity of -Regular List Colouring and a number of related colouring problems for graphs with bounded maximum degree.     

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 size-Ramsey number of powers of paths

Given graphs and and a positive integer , say that is -Ramsey for , denoted , if every -coloring of the edges of contains a monochromatic copy of . The size-Ramsey number of a graph is defined to be . Answering a question of Conlon, we prove that, for every fixed , we have , where is the th power of the -vertex path (ie, the graph with vertex set and all edges such that the distance between and in is at most ). Our proof is probabilistic, but can also be made constructive.     

On -connected graphs

A graph is called -connected if is -edge-connected and is -edge-connected for every vertex . The study of -connected graphs is motivated by a theorem of Thomassen [J. Combin. Theory Ser. A 110 (2015), pp. 67–78] (that was a conjecture of Frank [SIAM J. Discrete Math. 5 (1992), no. 1, pp. 25–53]), which states that a graph has a -vertex-connected orientation if and only if it is (2,2)-connected. In this paper, we provide a construction of the family of -connected graphs for even, which generalizes the construction given by Jordán [J. Graph Theory 52 (2006), pp. 217–229] for (2,2)-connected graphs. We also solve the corresponding connectivity augmentation problem: given a graph and an integer , what is the minimum number of edges to be added to make -connected. Both these results are based on a new splitting-off theorem for -connected graphs.     

On perfect matchings in matching covered graphs

A graph is matching-covered if every edge of is contained in a perfect matching. A matching-covered graph is strongly coverable if, for any edge of , the subgraph is still matching-covered. An edge subset of a matching-covered graph is feasible if there exist two perfect matchings and such that , and an edge subset with at least two edges is an equivalent set if a perfect matching of contains either all edges in or none of them. A strongly matchable graph does not have an equivalent set, and any two independent edges of form a feasible set. In this paper, we show that for every integer , there exist infinitely many -regular graphs of class 1 with an arbitrarily large equivalent set that is not switching-equivalent to either or , which provides a negative answer to a problem of Lukot’ka and Rollová. For a matching-covered bipartite graph , we show that has an equivalent set if and only if it has a 2-edge-cut that separates into two balanced subgraphs, and is strongly coverable if and only if every edge-cut separating into two balanced subgraphs and satisfies and .     

Online Ramsey theory for a triangle on -free graphs

Given a class of graphs and a fixed graph , the online Ramsey game for H on is a game between two players Builder and Painter as follows: an unbounded set of vertices is given as an initial state, and on each turn Builder introduces a new edge with the constraint that the resulting graph must be in , and Painter colors the new edge either red or blue. Builder wins the game if Painter is forced to make a monochromatic copy of at some point in the game. Otherwise, Painter can avoid creating a monochromatic copy of forever, and we say Painter wins the game. We initiate the study of characterizing the graphs such that for a given graph , Painter wins the online Ramsey game for on -free graphs. We characterize all graphs such that Painter wins the online Ramsey game for on the class of -free graphs, except when is one particular graph. We also show that Painter wins the online Ramsey game for on the class of -minor-free graphs, extending a result by Grytczuk, Hałuszczak, and Kierstead [Electron. J. Combin. 11 (2004), p. 60].     

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.     

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.     

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.     

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.     

Bipartite spanning sub(di)graphs induced by 2-partitions

For a given -partition of the vertices of a (di)graph , we study properties of the spanning bipartite subdigraph of induced by those arcs/edges that have one end in each . We determine, for all pairs of nonnegative integers , the complexity of deciding whether has a 2-partition such that each vertex in (for ) has at least (out-)neighbours in . We prove that it is -complete to decide whether a digraph has a 2-partition such that each vertex in has an out-neighbour in and each vertex in has an in-neighbour in . The problem becomes polynomially solvable if we require to be strongly connected. We give a characterisation of the structure of -complete instances in terms of their strong component digraph. When we want higher in-degree or out-degree to/from the other set, the problem becomes -complete even for strong digraphs. A further result is that it is -complete to decide whether a given digraph has a -partition such that is strongly connected. This holds even if we require the input to be a highly connected eulerian digraph.     

Reconstruction from the deck of -vertex induced subgraphs

The - deck of a graph is its multiset of subgraphs induced by vertices; we study what can be deduced about a graph from its -deck. We strengthen a result of Manvel by proving for that when is large enough ( suffices), the -deck determines whether an -vertex graph is connected ( suffices when , and cannot suffice). The reconstructibility of a graph with vertices is the largest such that is determined by its -deck. We generalize a result of Bollobás by showing for almost all graphs. As an upper bound on , we have . More generally, we compute whenever , which involves extending a result of Stanley. Finally, we show that a complete -partite graph is reconstructible from its -deck.     

A dichotomy for the kernel by H-walks problem in digraphs

Let be a digraph which may contain loops, and let be a loopless digraph with a coloring of its arcs . An -walk of is a walk of such that is an arc of , for every . For , we say that reaches by -walks if there exists an -walk from to in . A subset is a kernel by -walks of if every vertex in reaches by -walks some vertex in , and no vertex in can reach another vertex in by -walks. A panchromatic pattern is a digraph such that every -arc-colored digraph has a kernel by -walks. In this study, we prove that every digraph is either a panchromatic pattern, or the problem of determining whether an arc-colored digraph has a kernel by -walks is -complete.     

Distance matching extension and local structure of graphs

A matching in a graph is said to be extendable if there exists a perfect matching of containing . Also, is said to be a distance matching if the shortest distance between a pair of edges in is at least . A graph is distance matchable if every distance matching is extendable in , regardless of its size. In this paper, we study the class of distance matchable graphs. In particular, we prove that for every integer with , there exists a positive integer such that every connected, locally -connected -free graph of even order is distance matchable. We also prove that every connected, locally -connected -free graph of even order is distance matchable. Furthermore, we make more detailed analysis of -free graphs and study their distance matching extension properties.     

Improper coloring of graphs on surfaces

A graph is -colorable if its vertex set can be partitioned into sets , such that for each , the subgraph of induced by has maximum degree at most . The Four Color Theorem states that every planar graph is -colorable, and a classical result of Cowen, Cowen, and Woodall shows that every planar graph is -colorable. In this paper, we extend both of these results to graphs on surfaces. Namely, we show that every graph embeddable on a surface of Euler genus is -colorable and -colorable. Moreover, these graphs are also -colorable and -colorable. We also prove that every triangle-free graph that is embeddable on a surface of Euler genus is -colorable. This is an extension of Grötzsch's Theorem, which states that triangle-free planar graphs are -colorable. Finally, we prove that every graph of girth at least 7 that is embeddable on a surface of Euler genus is -colorable. All these results are best possible in several ways as the girth condition is sharp, the constant maximum degrees cannot be improved, and the bounds on the maximum degrees depending on are tight up to a constant multiplicative factor.     

Strong chromatic index of unit distance graphs

The strong chromatic index of a graph , denoted by , is defined as the least number of colors in a coloring of edges of , such that each color class is an induced matching (or: if edges and have the same color, then both vertices of are not adjacent to any vertex of ). A graph is a unit distance graph in if vertices of can be uniquely identified with points in , so that is an edge of if and only if the Euclidean distance between the points identified with and is 1. We would like to find the largest possible value of , where is a unit distance graph (in and ) of maximum degree . We show that , where is a unit distance graph in of maximum degree . We also show that the maximum possible size of a strong clique in unit distance graph in is linear in and give a tighter result for unit distance graphs in the plane.     

The Ramsey number of loose cycles versus cliques

Let be the Ramsey number of an -uniform loose cycle of length versus an -uniform clique of order . Kostochka et al. showed that for each fixed , the order of magnitude of is up to a polylogarithmic factor in . They conjectured that for each we have . We prove that , and more generally for every that . We also prove that for every and , if is odd, which improves upon the result of Collier-Cartaino et al. who proved that for every and we have .     

The average degree of a subcubic edge-chromatic critical graph

A graph is here called 3- critical if , and for every edge of . The 3-critical graphs include (the Petersen graph with a vertex deleted), and subcubic graphs that are Hajós joins of copies of . Building on a recent paper of Cranston and Rabern, it is proved here that if is 3-critical and not nor a Hajós join of two copies of , then has average degree at least ; this bound is sharp, as it is the average degree of a Hajós join of three copies of .