Shotgun reconstruction in the hypercube

Mossel and Ross raised the question of when a random coloring of a graph can be reconstructed from local information, namely, the colorings (with multiplicity) of balls of given radius. In this article, we are concerned with random 2-colorings of the vertices of the -dimensional hypercube, or equivalently random Boolean functions. In the worst case, balls of diameter are required to reconstruct. However, the situation for random colorings is dramatically different: we show that almost every 2-coloring can be reconstructed from the multiset of colorings of balls of radius 2. Furthermore, we show that for , almost every -coloring can be reconstructed from the multiset of colorings of 1-balls.     

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

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 .     

Phase transitions in graphs on orientable surfaces

Let be the orientable surface of genus and denote by the class of all graphs on vertex set with edges embeddable on . We prove that the component structure of a graph chosen uniformly at random from features two phase transitions. The first phase transition mirrors the classical phase transition in the Erd?s‐Rényi random graph chosen uniformly at random from all graphs with vertex set and edges. It takes place at , when the giant component emerges. The second phase transition occurs at , when the giant component covers almost all vertices of the graph. This kind of phenomenon is strikingly different from and has only been observed for graphs on surfaces.     

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.     

On the cycle space of a random graph

Write for the cycle space of a graph G, for the subspace of spanned by the copies of the κ‐cycle in G, for the class of graphs satisfying , and for the class of graphs each of whose edges lies in a . We prove that for every odd and , so the 's of a random graph span its cycle space as soon as they cover its edges. For κ = 3 this was shown in [6].     

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.     

Upper bounds on the uniquely restricted chromatic index

Golumbic, Hirst, and Lewenstein define a matching in a simple, finite, and undirected graph to be uniquely restricted if no other matching covers exactly the same set of vertices. We consider uniquely restricted edge-colorings of , defined as partitions of its edge set into uniquely restricted matchings, and study the uniquely restricted chromatic index of , defined as the minimum number of uniquely restricted matchings required for such a partition. For every graph , where is the classical chromatic index, the acyclic chromatic index, and the strong chromatic index of . While Vizing's famous theorem states that is either the maximum degree of or , two famous open conjectures due to Alon, Sudakov, and Zaks, and to Erdős and Nešetřil concern upper bounds on and in terms of . Since is sandwiched between these two parameters, studying upper bounds in terms of is a natural problem. We show that with equality if and only if some component of is . If is connected, bipartite, and distinct from , and is at least , then, adapting Lovász's elegant proof of Brooks’ theorem, we show that . Our proofs are constructive and yield efficient algorithms to determine the corresponding edge-colorings.     

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.     

Counting restricted orientations of random graphs

We count orientations of avoiding certain classes of oriented graphs. In particular, we study , the number of orientations of the binomial random graph in which every copy of is transitive, and , the number of orientations of containing no strongly connected copy of . We give the correct order of growth of and up to polylogarithmic factors; for orientations with no cyclic triangle, this significantly improves a result of Allen, Kohayakawa, Mota, and Parente. We also discuss the problem for a single forbidden oriented graph, and state a number of open problems and conjectures.     

Long properly coloured cycles in edge-coloured graphs

Let be an edge-coloured graph. The minimum colour degree of is the largest integer such that, for every vertex , there are at least distinct colours on edges incident to . We say that is properly coloured if no two adjacent edges have the same colour. In this paper, we show that, for any and large, every edge-coloured graph with contains a properly coloured cycle of length at least .     

Minimum codegree condition for perfect matchings in k-partite k-graphs

Let be a -partite -graph with vertices in each partition class, and let denote the minimum codegree of . We characterize those with and with no perfect matching. As a consequence, we give an affirmative answer to the following question of Rödl and Ruciński: if is even or , does imply that has a perfect matching? We also give an example indicating that it is not sufficient to impose this degree bound on only two types of -sets.     

Extending edge-colorings of complete hypergraphs into regular colorings

Let be the collection of all -subsets of an -set . Given a coloring (partition) of a set , we are interested in finding conditions under which this coloring is extendible to a coloring of so that the number of times each element of appears in each color class (all sets of the same color) is the same number . The case was studied by Sylvester in the 18th century and remained open until the 1970s. The case is extensively studied in the literature and is closely related to completing partial symmetric Latin squares. For , we settle the cases , and completely. Moreover, we make partial progress toward solving the case where . These results can be seen as extensions of the famous Baranyai’s theorem, and make progress toward settling a 40-year-old problem posed by Cameron.     

Maximizing the mean subtree order

This article focuses on properties and structures of trees with maximum mean subtree order in a given family; such trees are called optimal in the family. Our main goal is to describe the structure of optimal trees in and , the families of all trees and caterpillars, respectively, of order . We begin by establishing a powerful tool called the Gluing Lemma, which is used to prove several of our main results. In particular, we show that if is an optimal tree in or for , then every leaf of is adjacent to a vertex of degree at least . We also use the Gluing Lemma to answer an open question of Jamison and to provide a conceptually simple proof of Jamison's result that the path has minimum mean subtree order among all trees of order . We prove that if is optimal in , then the number of leaves in is and that if is optimal in , then the number of leaves in is . Along the way, we describe the asymptotic structure of optimal trees in several narrower families of trees.     

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.     

An improvement on the maximum number of -dominating independent sets

Erdős and Moser raised the question of determining the maximum number of maximal cliques or, equivalently, the maximum number of maximal independent sets in a graph on vertices. Since then there has been a lot of research along these lines. A -dominating independent set is an independent set such that every vertex not contained in has at least neighbors in . Let denote the maximum number of -dominating independent sets in a graph on vertices, and let . Nagy initiated the study of . In this study, we disprove a conjecture of Nagy using a graph product construction and prove that for any even we have We also prove that for any we have improving the upper bound of Nagy.     

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.     

Size Ramsey numbers of stars versus cliques

The size Ramsey number of two graphs and is the smallest integer such that there exists a graph on edges with the property that every red-blue colouring of the edges of yields a red copy of or a blue copy of . In 1981, Erdős observed that and he conjectured that this upper bound on is sharp. In 1983, Faudree and Sheehan extended this conjecture as follows: They proved the case . In 2001, Pikhurko showed that this conjecture is not true for and , by disproving the mentioned conjecture of Erdős. Here, we prove Faudree and Sheehan's conjecture for a given and .     

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.