An official website of the United States government
Abstract A graph is said to be ‐free if it does not contain any subdivision of as an induced subgraph. Lévêque, Maffray and Trotignon conjectured that every ‐free graph is 4‐colorable. In this paper, we show that this conjecture is true for the class of {, diamond, bowtie}‐free graphs, where a diamond is the graph obtained from by removing one edge and a bowtie is the graph consisting of two triangles with one vertex identified.
more »
« less
Bounds on Ramsey games via alterations
Abstract We present a refinement of the classical alteration method for constructing ‐free graphs for suitable edge‐probabilities , we show that removing all edges in ‐copies of the binomial random graph does not significantly change the independence number. This differs from earlier alteration approaches of Erdős and Krivelevich, who obtained similar guarantees by removing one edge from each ‐copy (instead of all of them). We demonstrate the usefulness of our refined alternation method via two applications to online graph Ramsey games, where it enables easier analysis.
more »
« less
- PAR ID:
- 10419080
- Publisher / Repository:
- Wiley Blackwell (John Wiley & Sons)
- Date Published:
- Journal Name:
- Journal of Graph Theory
- Volume:
- 104
- Issue:
- 3
- ISSN:
- 0364-9024
- Page Range / eLocation ID:
- p. 470-484
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract We use graph theory simulations and single molecule experiments to investigate percolation properties of kinetoplasts, the topologically linked mitochondrial DNA from trypanosome parasites. The edges of some kinetoplast networks contain a fiber of redundantly catenated DNA loops, but previous investigations of kinetoplast topology did not take this into account. Our graph simulations track the size of connected components in lattices as nodes are removed, analogous to the removal of minicircles from kinetoplasts. We find that when the edge loop is taken into account, the largest component after the network de‐percolates is a remnant of the edge loop, before it undergoes a second percolation transition and breaks apart. This implies that stochastically removing minicircles from kinetoplast DNA would isolate large polycatenanes, which is observed in experiments that use photonicking to stochastically destroy kinetoplasts fromCrithidia fasciculata. Our results imply kinetoplasts may be used as a source of linear polycatenanes for future experiments.more » « less
-
A hole in a graph $$G$$ is an induced cycle of length at least four, and an even hole is a hole of even length. The diamond is the graph obtained from the complete graph $$K_4$$ by removing an edge. A pyramid is a graph consisting of a vertex $$a$$ called the apex and a triangle $$\{b_1, b_2, b_3\}$$ called the base, and three paths $$P_i$$ from $$a$$ to $$b_i$$ for $$1 \leq i \leq 3$$, all of length at least one, such that for $$i \neq j$$, the only edge between $$P_i \setminus \{a\}$$ and $$P_j \setminus \{a\}$$ is $$b_ib_j$$, and at most one of $$P_1$$, $$P_2$$, and $$P_3$$ has length exactly one. For a family $$\mathcal{H}$$ of graphs, we say a graph $$G$$ is $$\mathcal{H}$$-free if no induced subgraph of $$G$$ is isomorphic to a member of $$\mathcal{H}$$. Cameron, da Silva, Huang, and Vušković proved that (even hole, triangle)-free graphs have treewidth at most five, which motivates studying the treewidth of even-hole-free graphs of larger clique number. Sintiari and Trotignon provided a construction of (even hole, pyramid, $$K_4$$)-free graphs of arbitrarily large treewidth. Here, we show that for every $$t$$, (even hole, pyramid, diamond, $$K_t$$)-free graphs have bounded treewidth. The graphs constructed by Sintiari and Trotignon contain diamonds, so our result is sharp in the sense that it is false if we do not exclude diamonds. Our main result is in fact more general, that treewidth is bounded in graphs excluding certain wheels and three-path-configurations, diamonds, and a fixed complete graph. The proof uses “non-crossing decompositions” methods similar to those in previous papers in this series. In previous papers, however, bounded degree was a necessary condition to prove bounded treewidth. The result of this paper is the first to use the method of “non-crossing decompositions” to prove bounded treewidth in a graph class of unbounded maximum degree.more » « less
-
Abstract Assouad–Nagata dimension addresses both large‐ and small‐scale behaviors of metric spaces and is a refinement of Gromov's asymptotic dimension. A metric space is a minor‐closed metric if there exists an (edge‐)weighted graph satisfying a fixed minor‐closed property such that the underlying space of is the vertex‐set of , and the metric of is the distance function in . Minor‐closed metrics naturally arise when removing redundant edges of the underlying graphs by using edge‐deletion and edge‐contraction. In this paper, we determine the Assouad–Nagata dimension of every minor‐closed metric. Our main theorem simultaneously generalizes known results about the asymptotic dimension of ‐minor free unweighted graphs and about the Assouad–Nagata dimension of complete Riemannian surfaces with finite Euler genus (Bonamy et al., Asymptotic dimension of minor‐closed families and Assouad–Nagata dimension of surfaces,JEMS(2024)).more » « less
-
Abstract A conjecture of Milena Mihail and Umesh Vazirani (Proc. 24th Annu. ACM Symp. Theory Comput., ACM, Victoria, BC, 1992, pp. 26–38.) states that the edge expansion of the graph of every polytope is at least one. Any lower bound on the edge expansion gives an upper bound for the mixing time of a random walk on the graph of the polytope. Such random walks are important because they can be used to generate an element from a set of combinatorial objects uniformly at random. A weaker form of the conjecture of Mihail and Vazirani says that the edge expansion of the graph of a polytope in is greater than one over some polynomial function of . This weaker version of the conjecture would suffice for all applications. Our main result is that the edge expansion of the graph of arandompolytope in is at least with high probability.more » « less
