Search

1959, Erd\H os and Gallai proved the asymptotically optimal bound for the maximum number of edges in graphs not containing a path of a fixed length. Here, we study a rainbow version of their theorem, in which one considers k ≥ 1 graphs on a common set of vertices not creating a path having edges from different graphs and asks for the maximum number of edges in each graph. We prove the asymptotically optimal bound in the case of a path on three edges and any k ≥ 1. [ABSTRACT FROM AUTHOR]

In this paper we prove several results on Ramsey numbers R(H,F) for a fixed graph H and a large graph F, in particular for F = Kn. These results extend earlier work of Erd\H os, Faudree, Rousseau, and Schelp and of Balister, Schelp, and Simonovits on so-called Ramsey sizelinear graphs. Among other results, we show that if H is a subdivision of K4 with at least six vertices, then R(H,F) =O(v(F)+e(F)) for every graph F. We also conjecture that if H is a connected graph with e(H) v(H) (k+1/2)2, then R(H,Kn) = O(nk). The case k = 2 was proved by Erd\H os, Faudree, Rousseau, and Schelp. We prove the case k = 3. [ABSTRACT FROM AUTHOR]

The circumference of a graph G with at least one cycle is the length of a longest cycle in G. A classic result of Birmel\'e [J. Graph Theory, 43 (2003), pp. 24--25] states that the treewidth of G is at most its circumference minus 1. In case G is 2-connected, this upper bound also holds for the pathwidth of G; in fact, even the treedepth of G is upper bounded by its circumference (Bria\'nski et al. [Treedepth vs circumference, Combinatorica, 43 (2023), pp. 659--664]). In this paper, we study whether similar bounds hold when replacing the circumference of G by its cocircumference, defined as the largest size of a bond in G, an inclusionwise minimal set of edges F such that G F has more components than G. In matroidal terms, the cocircumference of G is the circumference of the bond matroid of G. Our first result is the following "dual" version of Birmel'e's theorem: The treewidth of a graph G is at most its cocircumference. Our second and main result is an upper bound of 3k 2 on the pathwidth of a 2-connected graph G with cocircumference k. Contrary to circumference, no such bound holds for the treedepth of G. Our two upper bounds are best possible up to a constant factor. [ABSTRACT FROM AUTHOR]

Robinson space is a dissimilarity space (X, d) (i.e., a set X of size n and a dissimilarity d on X) for which there exists a total order < on X such that x < y < z implies that d(x, z) \geq max\{ d(x, y), d(y, z)\}. Recognizing if a dissimilarity space is Robinson has numerous applications in seriation and classification. An mmodule of (X, d) (generalizing the notion of a module in graph theory) is a subset M of X which is not distinguishable from the outside of M; i.e., the distance from any point of X \setminus M to all points of M is the same. If p is any point of X, then \{ p\}, and the maximal-by-inclusion mmodules of (X, d) not containing p define a partition of X, called the copoint partition. In this paper, we investigate the structure of mmodules in Robinson spaces and use it and the copoint partition to design a simple and practical divide-and-conquer algorithm for recognition of Robinson spaces in optimal O(n²) time. [ABSTRACT FROM AUTHOR]

For integers k ≥1 and m ≥2, let g(k,m) be the least integer n ≥1 such that every graph with chromatic number at least n contains a (k + 1)-connected subgraph with chromatic number at least m. Refining the recent result of Gir\~ao and Narayanan [Bull. Lond. Math. Soc., 54 (2022), pp. 868--875] that g(k 1, k) ≤ 7k + 1 for all k≥ 2, we prove that g(k,m) ≤ max(m + 2k 2, (3 + 1/16)k≤) for all k ≥ 1 and m≥2. This sharpens earlier results of Alon et al. [J. Graph Theory, 11 (1987), pp. 367-371], of Chudnovsky [J. Combin. Theory Ser. B, 103 (2013), pp. 567-586], and of Penev, Thomass'e, and Trotignon [SIAM J. Discrete Math., 30 (2016), pp. 592--619]. Our result implies that g(k, k + 1) (3 + 1/16)k for all k \geq 1, making a step closer towards a conjecture of Thomassen [J. Graph Theory, 7 (1983), pp. 261--271] that g(k, k +1)≤3k +1, which was originally a result with a false proof and was the starting point of this research area. [ABSTRACT FROM AUTHOR]

We establish a connection between tangles, a concept from structural graph theory that plays a central role in Robertson and Seymour's graph minor project, and hierarchical clustering. Tangles cannot only be defined for graphs, but in fact for arbitrary connectivity functions, which are functions defined on the subsets of some finite universe. In typical clustering applications, these universes consist of points in some metric space. Connectivity functions are usually required to be submodular. It is our first contribution to show that the central duality theorem connecting tangles with hierarchical decompositions (so-called branch decompositions) also holds if submodularity is replaced by a different property that we call maximum-submodular. We then define a connectivity function on finite data sets in an arbitrary metric space and prove that its tangles are in one-to-one correspondence with the clusters obtained by applying the well-known single linkage clustering algorithms to the same data set. Last, we generalize this correspondence for any hierarchical clustering. We show that the data structure that represents hierarchical clustering results, called dendograms, are equivalent to maximum-submodular connectivity functions and their tangles. The idea of viewing tangles as clusters was first proposed by Diestel and Whittle in 2016 as an approach to image segmentation. [ABSTRACT FROM AUTHOR]

A graph F is Ramsey for a pair of graphs (G,H) if any red/blue-coloring of the edges of F yields a copy of G with all edges colored red or a copy of H with all edges colored blue. Two pairs of graphs are called Ramsey equivalent if they have the same collection of Ramsey graphs. The symmetric setting, that is, the case G = H, received considerable attention. This led to the open question whether there are connected graphs G and G\prime such that (G,G) and (G' ,G') are Ramsey equivalent. We make progress on the asymmetric version of this question and identify several nontrivial families of Ramsey equivalent pairs of connected graphs. Certain pairs of stars provide a first, albeit trivial, example of Ramsey equivalent pairs of connected graphs. Our first result characterizes all Ramsey equivalent pairs of stars. The rest of the paper focuses on pairs of the form (T,Kt), where T is a tree and Kt is a complete graph. We show that if T belongs to a certain family of trees, including all nontrivial stars, then (T,Kt) is Ramsey equivalent to a family of pairs of the form (T,H), where H is obtained from Kt by attaching disjoint smaller cliques to some of its vertices. In addition, we establish that for (T,H) to be Ramsey equivalent to (T,Kt), H must have roughly this form. On the other hand, we prove that for many other trees T, including all odd-diameter trees, (T,Kt) is not equivalent to any such pair, not even to the pair (T,Kt K2), where Kt K2 is a complete graph Kt with a single edge attached. [ABSTRACT FROM AUTHOR]

The Caccetta--Häggkvist conjecture (denoted CHC) states that the directed girth (the smallest length of a directed cycle) dgirth(D) of a directed graph D on n vertices is at most... where δ+(D) is the minimum outdegree of D. We consider a version involving all outdegrees, not merely the minimum one, and prove that if D does not contain a sink, then dgirth(D) ≤... In the spirit of a generalization of the CHC to rainbow cycles in [1], this suggests the conjecture that given nonempty sets F1, . . ., Fn of edges of Kn, there exists a rainbow cycle of length at most... We prove a bit stronger result when 1 ≤ | Fi| ≤ 2, thereby strengthening a result of DeVos et al. [J. Graph Theory, 96 (2021), pp. 192--202]. We prove a logarithmic bound on the rainbow girth in the case that the sets Fi are triangles. [ABSTRACT FROM AUTHOR]

This work is a continuation of our previous work [D. M. Ha and H. T. Ngo. Int. J. Math., 34 (2023)], studying the expanding phenomenon in matrices over a finite chain ring with large residue field. A sum-product estimate is proved. It is shown that xy+z+t is a very strong expander, and that x(y + z) and xyz + x are moderate expanders of exponent 13. These results generalize the works of Le and Nguyen (see [J. Number. Theory, 216 (2020), pp. 174--191] and [Discrete Appl. Math., 322 (2022), pp. 166--170]. The solvability in large subsets of the equation xy = z + t is obtained, providing an answer to a question raised by Gyarmati and S\'ark\"ozy [Acta Math. Hungar., 119 (2008), pp. 259--280]. The proofs use spectral graph theory and elementary divisor theory. [ABSTRACT FROM AUTHOR]

Thomassen [J. Combin. Theory Ser. B, 141 (2020), pp. 343--351] asked whether every r-edge-connected r-regular graph of even order has r 2 pairwise disjoint perfect matchings. We show that this is not the case if r = 2 mod 4. Together with a recent result of Mattiolo and Steffen [J. Graph Theory, 99 (2022), pp. 107--116] this solves Thomassen's problem for all even r. It turns out that our methods are limited to the even case of Thomassen's problem. We then prove some equivalences of statements on pairwise disjoint perfect matchings in highly edge-connected regular graphs, where the perfect matchings contain or avoid fixed sets of edges. Based on these results we relate statements on pairwise disjoint perfect matchings of 5-edge-connected 5-regular graphs to well-known conjectures for cubic graphs, such as the Fan--Raspaud conjecture, the Berge--Fulkerson conjecture, and the 5-cycle double cover conjecture. [ABSTRACT FROM AUTHOR]

The transversal number Τ (H) of a hypergraph H is the minimum number of vertices that intersect every edge of H. A 6-uniform hypergraph has all edges of size 6. On 10 November 2000 Tuza and Vestergaard [Discuss. Math. Graph Theory, 22 (2002), pp. 199-210] conjectured that if H is a 3-regular 6-uniform hypergraph of order n, then Τ(H) < 1/4n. In this paper we prove this conjecture, which has become known as the Tuza-Vestergaard conjecture. [ABSTRACT FROM AUTHOR]

Denote by qn (G) the smallest eigenvalue of the signless Laplacian matrix of an n-vertex graph G. Brandt conjectured in 1997 that for regular triangle-free graphs qn(G) =4n/25 · We prove a stronger result: If G is a triangle-free graph, then qn(G) = 15n/94 < 4n/25 Brandt's conjecture is a subproblem of two famous conjectures of Erdőos: (1) Sparse-half-conjecture: Every n-vertex triangle-free graph has a subset of vertices of size [n\2] spanning at most n²/50 edges. (2) Every n-vertex triangle-free graph can be made bipartite by removing at most n²/25 edges. In our proof we use linear algebraic methods to upper bound qn(G) by the ratio between the number of induced paths with 3 and 4 vertices. We give an upper bound on this ratio via the method of flag algebras. [ABSTRACT FROM AUTHOR]

Given a graph G and a set T = {(si, ti): 1 = i = k} of k pairs, the VERTEX-DISJOINT PATHS (resp. EDGE-DISJOINT PATHS) problems asks to determine whether there exist pairwise vertex-disjoint (resp. edge-disjoint) paths P1,P2,...,Pk in G such that Pi connects si to ti for each 1 = i = k. Unlike their undirected counterparts which are FPT (parameterized by k) from Graph Minor theory, both the edge-disjoint and vertex-disjoint versions in directed graphs were shown by Fortune et al. (TCS '80) to be NP-hard for k = 2. This strong hardness for DISJOINT PATHS on general directed graphs led to the study of parameterized complexity on special graph classes, e.g., when the underlying undirected graph is planar. For VERTEX-DISJOINT PATHS on planar directed graphs, Schrijver (SICOMP '94) designed an nO(k) time algorithm which was later improved upon by Cygan et al. (FOCS '13) who designed an FPT algorithm running in 22O(k2) ·nO(1) time. To the best of our knowledge, the parameterized complexity of EDGE-DISJOINT PATHS on planar1 directed graphs is unknown. We resolve this gap by showing that EDGE-DISJOINT PATHS is W[1]-hard parameterized by the number k of terminal pairs, even when the input graph is a planar directed acyclic graph (DAG). This answers a question of Slivkins (ESA '03, SIDMA '10). Moreover, under the Exponential Time Hypothesis (ETH), we show that there is no f(k)· no(k) algorithm for EDGE-DISJOINT PATHS on planar DAGs, where k is the number of terminal pairs, n is the number of vertices and f is any computable function. Our hardness holds even if both the maximum in-degree and maximum out-degree of the graph are at most 2. [ABSTRACT FROM AUTHOR]

Let D=(V,A) be a digraph of order n. We define the degree of vertex v in D to be dD(v)=d+D(v)+d-D(v), where d+D(v) and d-D(v) are the out-degree and in-degree of v in D, respectively. Let k be a positive integer and let W be any given subset of V with |W|≥2k. In this paper we show that if dD(x)+dD(y)≥3n-3 for all {x,y}⊆W, then for any integer partition |W|=∑ki=1ni with ni≥2 for each i, there are k disjoint cycles containing exactly n1,...,nk vertices of W, respectively. The degree condition dD(x)+dD(y)≥3n-3 is sharp in some sense and this result confirms the conjecture posed by Wang [J. Graph Theory, 34 (2000), pp. 154-162] as a corollary. The result in this paper implies a theorem on cycle-factors containing matchings in bipartite graphs. Further, the special case W=V is a directed version of the Aigner-Brandt theorem on disjoint cycles in graphs. [ABSTRACT FROM AUTHOR]

We uncover a connection between two seemingly unrelated notions: lettericity, from structural graph theory, and geometric griddability, from the world of permutation patterns. Both of these notions capture important structural properties of their respective classes of objects. We prove that these notions are equivalent in the sense that a permutation class is geometrically griddable if and only if the corresponding class of inversion graphs has bounded lettericity. [ABSTRACT FROM AUTHOR]

A matching of a graph is a set of edges without common end vertex. A graph is called 1-planar if it admits a drawing in the plane such that each edge is crossed at most once. Recently, Biedl and Wittnebel [J. Graph Theory, 99 (2022), pp. 217--230] proved that every 1-planar graph with minimum degree 3 and n \geq 7 vertices has a matching of size at least n+12 7, which is tight for some graphs. They also provided tight lower bounds for the sizes of matchings in 1-planar graphs with minimum degree 4 or 5. In this paper, we show that any 1-planar graph with minimum degree 6 and n \geq 36 vertices has a matching of size at least 3n+4 7, and this lower bound is tight. Our result confirms a conjecture posed by Biedl and Wittnebel [J. Graph Theory, 99 (2022), pp. 217--230]. [ABSTRACT FROM AUTHOR]

Given an edge-colored graph, we say that a subgraph is rainbow if all of its edges have different colors. Let ex(n,H, rainbow-F) denote the maximal number of copies of H that a properly edge-colored graph on n vertices can contain if it has no rainbow subgraph isomorphic to F. We determine the order of magnitude of ex(n,Cs, rainbow-Ct) for all s, t with s ≠ = 3. In particular, we answer a question of Gerbner, Mészáros, Methuku, and Palmer by showing that ex(n,C2k, rainbow-C2k) is θ (nk-1) if k ≥ 3 and Θ (n²) if k = 2. We also determine the order of magnitude of ex(n, Pl, rainbow-C2k) for all k, l ≥ 2, where Pl denotes the path with l edges. [ABSTRACT FROM AUTHOR]

The graph parameter of pathwidth can be seen as a measure of the topological resemblance of a graph to a path. A popular definition of pathwidth is given in terms of node search, where we are given a system of tunnels (represented by a graph) that is contaminated by some infectious substance and we are looking for a search strategy that, at each step, either places a searcher on a vertex or removes a searcher from a vertex and where an edge is cleaned when both endpoints are simultaneously occupied by searchers. It was proved that the minimum number of searchers required for a successful cleaning strategy is equal to the pathwidth of the graph plus one. Two desired characteristics for a cleaning strategy are to be monotone (no recontamination occurs) and connected (clean territories always remain connected). Under these two demands, the number of searchers is equivalent to a variant of pathwidth called connected pathwidth. We prove that connected pathwidth is fixed parameter tractable; in particular we design a 2O(k2) \cdot n time algorithm that checks whether the connected pathwidth of G is at most k. This resolves an open question by Dereniowski, Osula, and Rz?azewski [Theoret. Comput. Sci., 794 (2019), pp. 85-100]. For our algorithm, we enrich the typical sequence technique that is able to deal with the connectivity demand. Typical sequences have been introduced by Bodlaender and Kloks [J. Algorithms, 21 (1996), pp. 358-402] for the design of linear parameterized algorithms for treewidth and pathwidth. While this technique has been later applied to other parameters, none of its advancements was able to deal with the connectivity demand, as it is a "global" demand that concerns an unbounded number of parts of the graph of unbounded size. The proposed extension is based on an encoding of the connectivity property that is quite versatile and may be adapted to deliver linear parameterized algorithms for the connected variants of other width parameters as well. An immediate consequence of our result is a 2O(k2) \cdot n time algorithm for the monotone and connected version of the edge search number. [ABSTRACT FROM AUTHOR]

The Weisfeiler--Leman procedure is a widely used technique for graph isomorphism testing that works by iteratively computing an isomorphism-invariant coloring of vertex tuples. Meanwhile, a fundamental tool in structural graph theory, which is often exploited in approaches to tackle the graph isomorphism problem, is the decomposition into 2- and 3-connected components. We prove that the two-dimensional Weisfeiler--Leman algorithm implicitly computes the decomposition of a graph into its 3-connected components. This implies that the dimension of the algorithm needed to distinguish two given nonisomorphic graphs is at most the dimension required to distinguish nonisomorphic 3-connected components of the graphs (assuming dimension at least 2). To obtain our decomposition result, we show that, for k ≥ 2, the k-dimensional algorithm distinguishes k-separators, i.e., k-tuples of vertices that separate the graph, from other vertex k-tuples. As a byproduct, we also obtain insights about the connectivity of constituent graphs of association schemes. In an application of the results, we show the new upper bound of k on the Weisfeiler--Leman dimension of the class of graphs of treewidth at most k. Using a construction by Cai, Fürer, and Immerman, we also provide a new lower bound that is asymptotically tight up to a factor of 2. [ABSTRACT FROM AUTHOR]

The notion of duality is a key element in understanding the interplay between the stability and chromatic numbers of a graph. This notion is a central aspect in the celebrated theory of perfect graphs and is further and deeply developed in the context of the Lovász theta function and its equivalent characterizations and variants. The main achievement of this paper is the introduction of a new family of norms, providing upper bounds for the stability number, that are obtained through duality from the norms motivated by Hoffman's lower bound for the chromatic number, and which achieve the (complementary) Lovász theta function at their optimum. As a consequence, our norms make it formal that Hoffman's bound for the chromatic number and the Delsarte-Hoffman ratio bound for the stability number are indeed dual. Further, we show that our new bounds strengthen the convex quadratic bounds for the stability number studied by Luz and Schrijver, and which achieve the Lovász theta function at their optimum. One of the key observations regarding weighted versions of these bounds is that, for any upper bound for the stability number of a graph which is a positive definite monotone gauge function, its gauge dual is a lower bound on the fractional chromatic number, and conversely. Our presentation is elementary and accessible to a wide audience. [ABSTRACT FROM AUTHOR]

Abelian group colorings were first introduced by Jaeger et al. in [J. Combin. Theory Ser. B, 56 (1992), pp. 165--182] as the dual concept of group connectivity of graphs. For given groups $\Gamma_1$ and $\Gamma_2$ with $|\Gamma_1| = |\Gamma_2|$, the dual version of a problem raised by Jaeger et al. suggests to investigate whether every $\Gamma_1$-colorable graph $G$ is also $\Gamma_2$-colorable. Recently, Husek, Mohelníková, and Šámal [J. Graph Theory, 93 (2019), pp. 317--327] used computer testing to find the first examples of $\mathbb{Z}_4$-connected but not $\mathbb{Z}_2^2$-connected graphs as well as $\mathbb{Z}_2^2$-connected but not $\mathbb{Z}_4$-connected graphs. As their examples are nonplanar, the group coloring problem remains unanswered. Group coloring was extended to non-abelian groups in Li and Lai [Discrete Math., 313 (2013), pp. 101--104]. We introduce a group coloring local structure (defined as a snarl in the paper) and use it to construct infinitely many ordered triples $(G, \Gamma_1, \Gamma_2)$ in which $G$ is a graph and $\Gamma_1$ and $\Gamma_2$ are groups with $|\Gamma_1| = |\Gamma_2|$, such that $G$ is $\Gamma_1$-colorable but not $\Gamma_2$-colorable. [ABSTRACT FROM AUTHOR]

Given an n-vertex graph H with minimum degree at least dn for some fixed d > 0, the distribution H\cup G(n, p) over the supergraphs of H is referred to as a (random) perturbation of H. We consider the distribution of edge-colored graphs arising from assigning each edge of the random perturbation H\cup G(n, p) a color, chosen independently and uniformly at random from a set of colors of size r := r(n). We prove that edge-colored graphs which are generated in this manner asymptotically almost surely admit rainbow Hamilton cycles whenever the edge-density of the random perturbation satisfies p := p(n)\geq C/n for some fixed C > 0 and r = (1 + o(1))n. The number of colors used is clearly asymptotically best possible. In particular, this improves on a recent result of Anastos and Frieze [J. Graph Theory, 92 (2019), pp. 405--414] in this regard. As an intermediate result, which may be of independent interest, we prove that randomly edge-colored sparse pseudorandom graphs asymptotically almost surely admit an almost spanning rainbow path. [ABSTRACT FROM AUTHOR]

Jerrum, Sinclair, and Vigoda [J. ACM, 51 (2004), pp. 671--697] showed that the permanent of any square matrix can be estimated in polynomial time. This computation can be viewed as approximating the partition function of edge-weighted matchings in a bipartite graph. Equivalently, this may be viewed as approximating the partition function of vertex-weighted independent sets in the line graph of a bipartite graph. Line graphs of bipartite graphs are perfect graphs and are known to be precisely the class of (claw, diamond, odd hole)-free graphs. So how far does the result of Jerrum, Sinclair, and Vigoda extend? We first show that it extends to (claw, odd hole)-free graphs, and then show that it extends to the even larger class of (fork, odd hole)-free graphs. Our techniques are based on graph decompositions, which have been the focus of much recent work in structural graph theory, and on structural results of Chv'atal and Sbihi [J. Combin. Theory Ser. B, 44 (1988)], Maffray and Reed [J. Combin. Theory Ser. B, 75 (1999)], and Lozin and Milaniv c [J. Discrete Algorithms, 6 (2008), pp. 595--604]. [ABSTRACT FROM AUTHOR]

A seminal result by Komlos, Sarkozy, and Szemeredi states that if a graph G with n vertices has minimum degree at least kn/(k + 1), for somek in N and n sufficiently large, then it contains the kth power of a Hamilton cycle. This is easily seen to be the largest power of a Hamilton cycle one can guarantee, given such a minimum degree assumption. Following a recent trend of studying effects of adding random edges to a dense graph, the model known as the randomly perturbed graph, Dudek et al. showed that if the minimum degree is at least kn(k + 1) + alpha n, for any constant alpha > 0, then adding O(n) random edges on top almost surely results in a graph which contains the (k + 1)st power of a Hamilton cycle. We show that the effect of these random edges is significantly stronger, namely, that one can almost surely find the (2k + 1)st power. This is the largest power one can guarantee in such a setting. [ABSTRACT FROM AUTHOR]

Guided by the theory of graph limits, we investigate a variant of the cut metric for limit objects of sequences of discrete probability distributions. Apart from establishing basic results, we introduce a natural operation called pinning on the space of limit objects and show how this operation yields a canonical cut metric approximation to a given probability distribution akin to the weak regularity lemma for graphons. We also establish the cut metric continuity of basic operations such as taking product measures. [ABSTRACT FROM AUTHOR]

Treedepth, a more restrictive graph width parameter than treewidth and pathwidth, plays a major role in the theory of sparse graph classes. We show that there exists a constant C such that for all positive integers a, b and a graph G, if the treedepth of G is at least Cab, then the treewidth of G is at least a or G contains a subcubic (i.e., of maximum degree at most 3) tree of treedepth at least b as a subgraph. As a direct corollary, we obtain that every graph of treedepth Omega (k3) either is of treewidth at least k, contains a subdivision of full binary tree of depth k, or contains a path of length 2k. This improves the bound of Omega (k5 log2 k) of Kawarabayashi and Rossman [Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 234--246]. We also show an application of our techniques for approximation algorithms of treedepth: given a graph G of treedepth k and treewidth t, one can in polynomial time compute a treedepth decomposition of G of width scrO (kt log3/2 t). This improves upon a bound of scrO (kt2 log t) stemming from a tradeoff between known results. The main technical ingredient in our result is a proof that every tree of treedepth d contains a subcubic subtree of treedepth at least d cdot log3((1 + surd 5)/2). [ABSTRACT FROM AUTHOR]

In 1969, Tucker characterized proper circular-arc graphs as those graphs whose augmented adjacency matrices have the circularly compatible ones property. Moreover, he also found a polynomial-time algorithm for deciding whether any given augmented adjacency matrix has the circularly compatible ones property. These results led to the first polynomial-time recognition algorithm for proper circular-arc graphs. However, as remarked there, this work did not solve the problems of finding a structure theorem and an efficient recognition algorithm for the circularly compatible ones property in arbitrary matrices (i.e., not restricted to augmented adjacency matrices only). In the present work, we solve these problems. More precisely, we give a minimal forbidden submatrix characterization for the circularly compatible ones property in arbitrary matrices and a linear-time recognition algorithm for the same property. We derive these results from analogous ones for the related D-circular property. Interestingly, these results lead to a minimal forbidden induced subgraph characterization and a linear-time recognition algorithm for proper circular-arc bigraphs, solving a problem first posed by Basu et al. [J. Graph Theory, 73 (2013), pp. 361--376]. Our findings generalize some known results about D-interval hypergraphs and proper interval bigraphs. [ABSTRACT FROM AUTHOR]

We disprove a conjecture of Nagy on the maximum number of copies N(G, H) of a fixed graph G in a large graph H with prescribed edge density. Nagy conjectured that for all G, the quantity N(G, H) is asymptotically maximized by either a quasi-star or a quasi-clique. We show this is false for infinitely many graphs, the smallest of which has six vertices and six edges. We also propose some new conjectures for the behavior of N(G, H) and present some evidence for them. [ABSTRACT FROM AUTHOR]

This paper deals with the characterization and the recognition of graph classes. A popular way to characterize a graph class is to list a minimal set of forbidden induced subgraphs. Unfortunately, this strategy rarely leads to a very efficient recognition algorithm. On the other hand, many graph classes can be efficiently recognized by techniques that use some ordering of the nodes, such as the one given by a traversal. We specifically study graphs that have an ordering avoiding some ordered structures. More precisely, we consider structures that we call patterns on three nodes, and we study the complexity of recognizing the classes associated with such patterns. In this domain, there are three key previous works. Independently Skrien [J. Graph Theory, 6 (1982), pp. 309-316] and Damashke [Forbidden ordered subgraphs, in Topics in Combinatorics and Graph Theory, Physica-Verlag HD, 1990, pp. 219--229] noted that several graph classes, such as chordal, bipartite, interval, and comparability graphs, have a characterization in terms of forbidden patterns. On the algorithmic side, Hell, Mohar, and Rafiey [Ordering without forbidden patterns, in Algorithms--ESA 2014, Springer, 2014, pp. 554--565] proved that any class defined by a set of forbidden patterns on three nodes can be recognized in time O(n3) by using an algorithm based on an extension of 2-SAT. We improve on these two lines of works by systematically characterizing all the classes defined by sets of forbidden patterns (on three nodes) and proving that among the 22 different classes (up to complement) that we find, 20 can actually be recognized in linear time. Beyond these results, we consider that this type of characterization is very useful from an algorithmic perspective, leads to a rich structure of classes, and generates many algorithmic and structural open questions worth investigating. [ABSTRACT FROM AUTHOR]

An edge-colored graph G is called rainbow if every edge of G receives a different color. The anti-Ramsey number of t edge-disjoint rainbow spanning trees, denoted by r(n, t), is defined as the maximum number of colors in an edge-coloring of Kn containing no t edge-disjoint rainbow spanning trees. Jahanbekam and West [J. Graph Theory, 82 (2016), pp. 75-89] conjectured that for any fixed t, r(n, t) = (n 2 2) + t whenever n geq 2t + 2 geq 6. In this paper, we prove this conjecture. We also determine r(n, t) when n = 2t+1. Together with previous results, this gives the anti-Ramsey number of t edge-disjoint rainbow spanning trees for all values of n and t. [ABSTRACT FROM AUTHOR]

Many basic properties in Tutte's flow theory for unsigned graphs do not have their counterparts for signed graphs. However, signed graphs without long barbells in many ways behave like unsigned graphs from the point view of flows. In this paper, we study whether some basic properties in Tutte's flow theory remain valid for this family of signed graphs. Specifically let (G, sigma) be a flow-admissible signed graph without long barbells. We show that it admits a nowhere-zero 6-flow and that it admits a nowhere-zero modulo k-flow if and only if it admits a nowhere-zero integer k-flow for each integer k geq 3 and k not = 4. We also show that each nowhere-zero positive integer k-flow of (G, sigma) can be expressed as the sum of some 2-flows. For general graphs, we show that every nowhere-zero p q -flow can be normalized in such a way, that each flow value is a multiple of 12q. As a consequence we prove the equality of the integer flow number and the ceiling of the circular flow number for flow-admissible signed graphs without long barbells. [ABSTRACT FROM AUTHOR]

One of the central topics in the theory of random graphs deals with the phase transition in the order of the largest components. In the binomial random graph scrG (n, p), the threshold for the appearance of the unique largest component (also known as the giant component) is pg = n 1. More precisely, when p changes from (1 varepsilon)pg (subcritical case) to pg and then to (1 + varepsilon)pg (supercritical case) for varepsilon > 0, with high probability the order of the largest component increases smoothly from O(varepsilon 2 log(varepsilon 3n)) to Theta (n2/3) and then to (1 pm o(1))2varepsilon n. Furthermore, in the supercritical case, with high probability the largest components except the giant component are trees of order O(varepsilon 2 log(varepsilon 3n)), exhibiting a structural symmetry between the subcritical random graph and the graph obtained from the supercritical random graph by deleting its giant component. As a natural generalization of random graphs and connectedness, we consider the binomial random k-uniform hypergraph scrH k(n, p) (where each k-tuple of vertices is present as a hyperedge with probability p independently) and the following notion of high-order connectedness. Given an integer 1 leq j leq k 1, two sets of j vertices are called j-connected if there is a walk of hyperedges between them such that any two consecutive hyperedges intersect in at least j vertices. A j-connected component is a maximal collection of pairwise j-connected j-tuples of vertices. Recently, the threshold for the appearance of the giant j-connected component in scrH k(n, p) and its order were determined. In this article, we take a closer look at the subcritical random hypergraph. We determine the structure, order, and size of the largest j-connected components, with the help of a certain class of "hypertrees"" and related objects. In our proofs, we combine various probabilistic and enumerative techniques, such as generating functions and couplings with branching processes. Our study will pave the way to establishing a symmetry between the subcritical random hypergraph and the hypergraph obtained from the supercritical random hypergraph by deleting its giant j-connected component. [ABSTRACT FROM AUTHOR]

An (n, s, q)-graph is an n-vertex multigraph where every set of s vertices spans at most q edges. In this paper, we determine the maximum product of the edge multiplicities in (n, s, q)-graphs if the congruence class of q modulo (s²) is in a certain interval of length about 3s/2. The smallest case that falls outside this range is (s, q) = (4, 15), and here the answer is an²+o(n²), where a is transcendental assuming Schanuel's conjecture. This could indicate the difficulty of solving the problem in full generality. Many of our results can be seen as extending work by Bondy and Tuza [J. Graph Theory, 25 (1997), pp. 267--275] and F&#252redi and K&#252ndgen [J. Graph Theory, 40 (2002), pp. 195--225] about sums of edge multiplicities to the product setting. We also prove a variety of other extremal results for (n, s, q)-graphs, including product-stability theorems. These results are of additional interest because they can be used to enumerate (n, s, q)-graphs. Our work therefore extends many classical enumerative results in extremal graph theory beginning with the Erdö s--Kleitman--Rothschild theorem [Asymptotic enumeration of Kn-free graphs, in Colloquio Internazionale sulle Teorie Combinatorie (Rome, 1973), Tomo II, Atti dei Convegni Lincei 17, Accad. Naz. Lincei, Rome, 1976, pp. 19--27] to multigraphs. [ABSTRACT FROM AUTHOR]

An edge-colored graph G is called rainbow if every edge of G receives a different color. The anti-Ramsey number of t edge-disjoint rainbow spanning trees, denoted by r(n,t), is defined as the maximum number of colors in an edge-coloring of Kn containing no t edge-disjoint rainbow spanning trees. Jahanbekam and West [J. Graph Theory, 2014] conjectured that for any fixed t, r(n,t)=(n-22)+t whenever n≥2t+2≥6. In this paper, we prove this conjecture. We also determine r(n,t) when n=2t+1. Together with previous results, this gives the anti-Ramsey number of t edge-disjoint rainbow spanning trees for all values of n and t. [ABSTRACT FROM AUTHOR]

A celebrated result of Mantel shows that every graph on n vertices with lfloor n2/4rfloor + 1 edges must contain a triangle. A robust version of this result, due to Rademacher, says that there must, in fact, be at least lfloor n/2rfloor triangles in any such graph. Another strengthening, due to the combined efforts of many authors starting with ErdH os, says that any such graph must have an edge which is contained in at least n/6 triangles. Following Mubayi, we study the interplay between these two results, that is, between the number of triangles in such graphs and their book number, the largest number of triangles sharing an edge. Among other results, Mubayi showed that for any 1/6 leq beta < 1/4 there is gamma > 0 such that any graph on n vertices with at least lfloor n2/4rfloor + 1 edges and book number at most beta n contains at least (gamma o(1))n3 triangles. He also asked for a more precise estimate for gamma in terms of beta. We make a conjecture about this dependency and prove this conjecture for beta = 1/6 and for 0.2495 leq beta < 1/4, thereby answering Mubayis question in these ranges. [ABSTRACT FROM AUTHOR]

Many of the tools developed for the theory of tree-decompositions of graphs do not work for directed graphs. In this paper we show that some of the most basic tools do work in the case where the model digraph is a directed path. Using these tools we define a notion of a directed blockage in a digraph and prove a min-max theorem for directed path-width analogous to the result of Bienstock, Roberston, Seymour, and Thomas for blockages in graphs. Furthermore, we show that every digraph with directed path width k contains each arboresence of order k+1 as a buttery minor. Finally we also show that every digraph admits a linked directed path-decomposition of minimum width, extending a result of Kim and Seymour on semi-complete digraphs. [ABSTRACT FROM AUTHOR]

We study the following version of cut sparsification. Given a large edge-weighted network G with k terminal vertices, compress it into a smaller network H with the same terminals, such that every minimum terminal cut in H approximates the corresponding one in G, up to a factor q > 1 that is called the quality. (The case q = 1 is known also as a mimicking network.) We provide new insights about the structure of minimum terminal cuts, leading to new results for cut sparsifiers of planar graphs. Our first contribution identifies a subset of the minimum terminal cuts, which we call elementary, that generates all the others. Consequently, H is a cut sparsifier if and only if it preserves all the elementary terminal cuts (up to this factor q). Our second and main contribution is to refine the known bounds in terms of 7 = 7(G), which is defined as the minimum number of faces that are incident to all the terminals in a planar graph G. We prove that the number of elementary terminal cuts is O((2/c/7)2"Y) (compared to O(2fc) terminal cuts) and furthermore obtain a mimicking network of size O(722"Y/c4), which is near-optimal as a function of 7. Our third contribution is a duality between cut sparsification and distance sparsification for certain planar graphs, when the sparsifier H is required to be a minor of G. This duality connects problems that were previously studied separately, implying new results, new proofs of known results, and equivalences between open gaps. [ABSTRACT FROM AUTHOR]

Let k be a positive integer. Bermond and Thomassen conjectured in 1981 that every digraph with minimum outdegree at least 2k 1 contains k vertex-disjoint cycles. This conjecture is famous as one of a hundred unsolved problems selected in [A. Bondy and M. R. Murty, Graph Theory, Springer-Verlag, London, 2008]. Lichiardopol, P\'or, and Sereni proved in [SIAM J. Discrete Math., 23 (2009), pp. 979--992] that the above conjecture holds for k = 3. Let g be the girth, i.e., the length of the shortest cycle, of a given digraph. Bang-Jensen, Bessy, and Thomass\'e conjectured in [J. Graph Theory, 75 (2014), pp. 284--302] that every digraph with girth g and minimum outdegree at least g g 1 k contains k vertex-disjoint cycles. Thomass\'e conjectured around 2006 that every oriented graph (a digraph without 2-cycles) with girth g and minimum outdegree at least h contains a path of length h(g 1), where h is a positive integer. In this paper, we first present a new shorter proof of the Bermond--Thomassen conjecture for the case of k = 3, and then we disprove the conjecture proposed by Bang-Jensen, Bessy, and Thomass\'e. Finally, we disprove the even girth case of the conjecture proposed by Thomass\'e. [ABSTRACT FROM AUTHOR]

For graphs H and F, let ex(n,H, F) be the maximum possible number of copies of H in an F-free graph on n vertices. The study of this function, which generalizes the well-studied Tur\'an numbers of graphs, was initiated recently by Alon and Shikhelman. We show that if F is a tree, then ex(n,H, F) =\Theta (nr) for an (explicit) integer r = r(H, F), thus answering one of their questions. [ABSTRACT FROM AUTHOR]

We consider the following natural "above-guarantee"" parameterization of the classical Longest Path problem: For given vertices s and t of a graph G and integer k, the Longest Detour problem asks for an (s, t)-path in G that is at least k longer than a shortest (s, t)-path. Using insights into structural graph theory, we prove that Longest Detour is fixed-parameter tractable on undirected graphs and actually even admits a single-exponential algorithm, that is, one of running time 2O(k)\cdot nO(1). Up to the base of the exponential, this running time matches the best algorithms for finding a path of length at least k. Furthermore, we study the related Exact Detour problem, which asks whether a graph G contains an (s, t)-path that is exactly k longer than a shortest (s, t)- path. For this problem, we obtain randomized algorithms with running times 2.746k\cdot nO(1) (for undirected graphs) and 4k\cdot nO(1) (for directed graphs) and a deterministic algorithm with running time 6.745k\cdot nO(1), showing that this problem is fixed-parameter tractable as well. [ABSTRACT FROM AUTHOR]

The notion of digits in finite fields was introduced a few years ago as an attempt to deliver insight in related yet unresolved questions over the natural numbers. Several such intractable questions are related to the sum of digits function, which assigns to every natural number the sum of its digits. Its analogue over finite fields, which is a map from Fq to Fp, q = ph where p prime and h = 2, has been studied by several authors. In particular, Cathy Swaenepoel [J. Number Theory, 189 (2018), pp. 97{114] investigated the sum of digits of products of field elements. The main techniques involved were estimates on certain character sums and Gaussian sums over Fq and Fp. In this paper, we extend and generalize these results using a different approach, based on spectral graph theory, without any reference to character theory. [ABSTRACT FROM AUTHOR]

In the theory of dense graph limits, a graphon is a symmetric measurable function W : [0, 1]2 \rightarrow [0, 1]. Each graphon gives rise naturally to a random graph distribution, denoted G(n,W), that can be viewed as a generalization of the Erd\H os--R\'enyi random graph. Recently, Dole\v zal, Hladk\'y, and M\'ath\'e gave an asymptotic formula of order log n for the clique number of G(n,W) when W is bounded away from 0 and 1. We show that if W is allowed to approach 1 at a finite number of points, and displays a moderate rate of growth near these points, then the clique number of G(n,W) will be \Theta (\surd n) almost surely. We also give a family of examples with clique number \Theta (n\alpha) for any \alpha \in (0, 1) and some conditions under which the clique number of G(n,W) will be o(\surd n), \omega (\surd n), or \Omega (n\alpha) for \alpha \in (0, 1). [ABSTRACT FROM AUTHOR]

We conjecture that every graph of minimum degree at least k 2 and maximum degree at least 2k contains all trees with k edges as subgraphs. We prove an approximate version of this conjecture for trees of bounded degree and dense host graphs. Our result relies on a general embedding tool for embedding trees into graphs of certain structure. This tool also has implications for the Erd\H os--S\'os conjecture and the 2 3 -conjecture. We prove an approximate version of both conjectures for bounded degree trees and dense host graphs. [ABSTRACT FROM AUTHOR]

The Cycle Packing problem asks whether a given undirected graph G = (V;E) con- tains k vertex-disjoint cycles. Since the publication of the classic Erd}os{Posa theorem in 1965, this problem received significant attention in the fields of graph theory and algorithm design. In particu- lar, this problem is one of the first problems studied in the framework of parameterized complexity. The nonuniform fixed-parameter tractability of Cycle Packing follows from the Robertson{Seymour theorem, a fact already observed by Fellows and Langston in the 1980s. In 1994, Bodlaender showed that Cycle Packing can be solved in time 2O(k2) jV j using exponential space. In the case a solu- tion exists, Bodlaender's algorithm also outputs a solution (in the same time). It has later become common knowledge that Cycle Packing admits a 2O(k log2 k) jV j-time (deterministic) algorithm using exponential space, which is a consequence of the Erd}os{Posa theorem. Nowadays, the design of this algorithm is given as an exercise in textbooks on parameterized complexity. Yet, no algorithm that runs in time 2o(k log2 k) jV jO(1), beating the bound 2O(k log2 k) jV jO(1), has been found. In light of this, it seems natural to ask whether the 2O(k log2 k) jV jO(1) bound is essentially optimal. In this paper, we answer this question negatively by developing a 2 O(k log2 k log log k) jV j-time (deterministic) algorithm for Cycle Packing. In the case a solution exists, our algorithm also outputs a solution (in the same time). Moreover, apart from beating the bound 2O(k log2 k) jV jO(1), our algorithm runs in time linear in jV j, and its space complexity is polynomial in the input size. [ABSTRACT FROM AUTHOR]

An ∊-distance-uniform graph is one with a critical distance d such that from every vertex, all but at most an ∊-fraction of the remaining vertices are at distance exactly d. Motivated by the theory of network creation games, Alon, Demaine, Hajiaghayi, and Leighton made the following conjecture of independent interest: that every ∊-distance-uniform graph (and, in fact, a broader class of ∊-distance-almost-uniform graphs) has critical distance at most logarithmic in the number of vertices n. We disprove this conjecture and characterize the asymptotics of this extremal problem. Specifically, for 1/n ≤ ∊ ≤ 1/logn, we construct ∊-distance-uniform graphs with critical distance 2Ω(logn/loge-1) 2O(logn/log e-1). We also prove an upper bound on the critical distance of the form 2Ologn/loge-1 for all e and n. Our lower bound construction introduces a novel method inspired by the Tower of Hanoi puzzle and may itself be of independent interest. [ABSTRACT FROM AUTHOR]

We continue the study of circuit covers of signed graphs initiated by Mačajová et al. [J. Graph Theory, 81 (2016), pp. 120--133] by investigating signed circuit covers of signed Eulerian graphs. A signed circuit cover of a signed graph is a collection of signed circuits such that each edge of the signed graph belongs to at least one of them. We prove that every signed Eulerian graph G that admits a signed circuit cover has one of length at most 3/2 · |E(G)|. We show that the bound is tight and characterize those graphs that reach it. This result stands in a sharp contrast with the unsigned case where the bound is 1 · |E(G)| (by the classical result of Veblen). For signed Eulerian graphs with an even number of negative edges we establish a better bound of 4/3 · |E(G)| and show that it is also tight. [ABSTRACT FROM AUTHOR]

A tight k-uniform l -cycle, denoted by TCkl, is a k-uniform hypergraph whose vertex set is v0, . . . , vl-1, and the edges are all the k-tuples {vi, vi+1, . . . , vi+k-1}, with subscripts modulo l . Motivated by a classic result in graph theory that every n-vertex cycle-free graph has at most n 1 edges, Sós and, independently, Verstraïte asked whether for every integer k, a k-uniform n-vertex hypergraph without any tight k-uniform cycles has at most (n-1 k-1) edges. In this paper, we answer this question in negative. [ABSTRACT FROM AUTHOR]

A variety of powerful extremal results have been shown for the chromatic number of triangle-free graphs. Three noteworthy bounds are in terms of the number of vertices, edges, and maximum degree given by Poljak and Tuza [SIAM J. Discrete Math., 7 (1994), pp. 307--313] and Johansson. There have been comparatively fewer works extending these types of bounds to graphs with a small number of triangles. One noteworthy exception is a result of Alon, Krivelevich, and Sudakov [J. Combin. Theory Ser. B, 77 (1999), pp. 73--82] bounding the chromatic number for graphs with low degree and few triangles per vertex; this bound is nearly the same as for triangle-free graphs. This type of parametrization is much less rigid and has appeared in dozens of combinatorial constructions. In this paper, we show a similar type of result for X (G) as a function of the number of vertices n, the number of edges m, as well as the triangle count (both local and global measures). Our results smoothly interpolate between the generic bounds true for all graphs and bounds for triangle-free graphs. Our results are tight for most of these cases; we show how an open problem regarding fractional chromatic number and degeneracy in triangle-free graphs can resolve the small remaining gap in our bounds. [ABSTRACT FROM AUTHOR]

conflict-free k-coloring of a graph assigns one of k different colors to some of the vertices such that, for every vertex v, there is a color that is assigned to exactly one vertex among v and v's neighbors. Such colorings have applications in wireless networking, robotics, and geometry and are well studied in graph theory. Here we study the natural problem of the conflict-free chromatic number Xchi CF (G) (the smallest k for which conflict-free k-colorings exist). We provide results both for closed neighborhoods N[v], for which a vertex v is a member of its neighborhood, and for open neighborhoods N(v), for which vertex v is not a member of its neighborhood. For closed neighborhoods, we prove the conflict-free variant of the famous Hadwiger Conjecture: If an arbitrary graph G does not contain Kk+1 as a minor, then Xchi CF (G) ≤ k. For planar graphs, we obtain a tight worst-case bound: three colors are sometimes necessary and always sufficient. In addition, we give a complete characterization of the algorithmic/computational complexity of conflict-free coloring. It is NP-complete to decide whether a planar graph has a conflict-free coloring with one color, while for outerplanar graphs, this can be decided in polynomial time. Furthermore, it is NP-complete to decide whether a planar graph has a conflict-free coloring with two colors, while for outerplanar graphs, two colors always suffice. For the bicriteria problem of minimizing the number of colored vertices subject to a given bound k on the number of colors, we give a full algorithmic characterization in terms of complexity and approximation for outerplanar and planar graphs. For open neighborhoods, we show that every planar bipartite graph has a conflict-free coloring with at most four colors; on the other hand, we prove that for k € { 1, 2, 3}, it is NP-complete to decide whether a planar bipartite graph has a conflict-free k-coloring. Moreover, we establish that any general planar graph has a conflict-free coloring with at most eight colors. [ABSTRACT FROM AUTHOR]

We determine, asymptotically in n, the distribution and mean of the weight of a minimum-weight k-clique (or any strictly balanced graph H) in a complete graph Kn whose edge weights are independent random values drawn from the uniform distribution or other continuous distributions. For the clique, we also provide explicit (nonasymptotic) bounds on the distribution's cumulative distribution function in a form obtained directly from the Stein{Chen method and in a looser but simpler form. The direct form extends to other subgraphs and other edge-weight distributions. We illustrate the clique results for various values of k and n. The results may be applied to evaluate whether an observed minimum-weight copy of a graph H in a network provides statistical evidence that the network's edge weights are not independently distributed but have some structure. [ABSTRACT FROM AUTHOR]