Search

A recent trend in the context of graph theory is to bring theoretical analyses closer to empirical observations by focusing the studies on random graph models that are used to represent practical instances. There, it was observed that geometric inhomogeneous random graphs (GIRGs) yield good representations of complex real-world networks by expressing edge probabilities as a function that depends on (heterogeneous) vertex weights and distances in some underlying geometric space that the vertices are distributed in. While most of the parameters of the model are understood well, it was unclear how the dimensionality of the ground space affects the structure of the graphs. In this paper, we complement existing research into the dimension of geometric random graph models and the ongoing study of determining the dimensionality of real-world networks by studying how the structure of GIRGs changes as the number of dimensions increases. We prove that, in the limit, GIRGs approach nongeometric inhomogeneous random graphs and present insights on how quickly the decay of the geometry impacts important graph structures. In particular, we study the expected number of cliques of a given size as well as the clique number and characterize phase transitions at which their behavior changes fundamentally. Finally, our insights help in better understanding previous results about the impact of the dimensionality on geometric random graphs. [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]

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]

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]

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]

In 1984, Erdős conjectured that the number of pentagons in any triangle-free graph on n vertices is at most (n/5)5, which is sharp by the balanced blow-up of a pentagon. This was proved by Grzesik, and independently by Hatami, Hladký, Král', Norine and Razborov. As an extension of this result for longer cycles, we prove that for each odd k ≥ 7, the balanced blow-up of Ck (uniquely) maximises the number of k-cycles among Ck-2-free graphs on n vertices, as long as n is sufficiently large. We also show that this is no longer true if n is not assumed to be sufficiently large. Our result strengthens results of Grzesik and Kielak who proved that for each odd k ≥ 7, the balanced blow-up of Ck maximises the number of k-cycles among graphs with a given number of vertices and no odd cycles of length less than k. We further show that if k and ℓ are odd and k is sufficiently large compared to ℓ, then the balanced blow-up of Cℓ+2 does not asymptotically maximise the number of k-cycles among Cℓ-free graphs on n vertices. This disproves a conjecture of Grzesik and Kielak. [ABSTRACT FROM AUTHOR]

We obtain lower and upper bounds for the maximum weight of a directed cut in the classes of weighted digraphs and weighted acyclic digraphs as well as in some of their subclasses. We compare our results with those obtained for the maximum size of a directed cut in unweighted digraphs. In particular, we show that a lower bound obtained by Alon, Bollob\'as, Gy\'arf\'as, Lehel, and Scott [J. Graph Theory, 55 (2007), pp. 1-13] for unweighted acyclic digraphs can be extended to weighted digraphs with the maximum length of a cycle being bounded by a constant and the weight of every arc being at least one. We state a number of open problems. [ABSTRACT FROM AUTHOR]

We provide a combinatorial and self-contained proof of a result following from G. Besson [Ann. Inst. Fourier, 30 (1980), pp. 109-128] and Y. Colin de Verdière [Ann. Sci. Ec. Norm. Supér., 20 (1987), pp. 599-615] that for all graphs G embedded on a surface S, the Colin de Verdière parameter μ(G) is upper bounded by 7-2χ(S). [ABSTRACT FROM AUTHOR]

For any hereditary graph class F, we construct optimal adjacency labeling schemes for the classes of subgraphs and induced subgraphs of Cartesian products of graphs in F. As a consequence, we show that, if F admits efficient adjacency labels (or, equivalently, small induced-universal graphs) meeting the information-theoretic minimum, then the classes of subgraphs and induced subgraphs of Cartesian products of graphs in F do too. Our proof uses ideas from randomized communication complexity, hashing, and additive combinatorics, and improves upon recent results of Chepoi, Labourel, and Ratel [Journal of Graph Theory, 2020]. [ABSTRACT FROM AUTHOR]

We consider the symmetric difference of two graphs on the same vertex set [n], which is the graph on [n] whose edge set consists of all edges that belong to exactly one of the two graphs. Let F be a class of graphs, and let MF(n) denote the maximum possible cardinality of a family G of graphs on [n] such that the symmetric difference of any two members in G belongs to F. These concepts have been recently investigated by Alon et al. [SIAM J. Discrete Math., 37 (2023), pp. 379-403] with the aim of providing a new graphic approach to coding theory. In particular, MF(n) denotes the maximum possible size of this code. Existing results show that as the graph class F changes, MF(n) can vary from n to 2(1+0(1))(2n). We study several phase transition problems related to MF(n) in general settings and present a partial solution to a recent problem posed by Alon et al. [ABSTRACT FROM AUTHOR]

We prove that every family of (not necessarily distinct) even cycles D1,...D⌊1.2(n-1)⌋+1 on some fixed n-vertex set has a rainbow even cycle (that is, a set of edges from distinct Di's, forming an even cycle). This resolves an open problem of Aharoni, Briggs, Holzman and Jiang. Moreover, the result is best possible for every positive integer n. [ABSTRACT FROM AUTHOR]

We show that if the edges or vertices of an undirected graph G can be covered by k shortest paths, then the pathwidth of G is upper-bounded by a single-exponential function of k. As a corollary, we prove that the problem ISOMETRIC PATH COVER WITH TERMINALS (which, given a graph G and a set of k pairs of vertices called terminals, asks whether G can be covered by k shortest paths, each joining a pair of terminals) is FPT with respect to the number of terminals. The same holds for the similar problem STRONG GEODETIC SET WITH TERMINALS (which, given a graph G and a set of k terminals, asks whether there exist (2k) shortest paths covering G, each joining a distinct pair of terminals). Moreover, this implies that the related problems ISOMETRIC PATH COVER and STRONG GEODETIC SET (defined similarly but where the set of terminals is not part of the input) are in XP with respect to parameter k. [ABSTRACT FROM AUTHOR]

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]

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]