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 .     

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.     

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.     

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.     

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.     

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.     

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 .     

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.     

Perfect divisibility and 2-divisibility

A graph G is said to be 2-divisible if for all (nonempty) induced subgraphs H of G, can be partitioned into two sets such that and . (Here denotes the clique number of G, the number of vertices in a largest clique of G). A graph G is said to be perfectly divisible if for all induced subgraphs H of G, can be partitioned into two sets such that is perfect and . We prove that if a graph is -free, then it is 2-divisible. We also prove that if a graph is bull-free and either odd-hole-free or P₅-free, then it is perfectly divisible.     

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

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.     

Polynomial relations between matrices of graphs

We derive a correspondence between the eigenvalues of the adjacency matrix and the signless Laplacian matrix of a graph when is -biregular by using the relation . This motivates asking when it is possible to have for a polynomial, , and matrices associated to a graph . It turns out that, essentially, this can only happen if is either regular or biregular.     

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.     

Counting degree sequences of spanning trees in bipartite graphs: A graph-theoretic proof

Given a bipartite graph with bipartition each spanning tree in has a degree sequence on and one on . Löhne and Rudloff showed that the number of possible degree sequences on equals the number of possible degree sequences on . Their proof uses a non-trivial characterization of degree sequences by -draconian sequences based on polyhedral results of Postnikov. In this paper, we give a purely graph-theoretic proof of their result.