An official website of the United States government
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
The chromatic number of {ISK4, diamond, bowtie}‐free graphs
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
- PAR ID:
- 10237879
- Publisher / Repository:
- Wiley Blackwell (John Wiley & Sons)
- Date Published:
- Journal Name:
- Journal of Graph Theory
- Volume:
- 96
- Issue:
- 4
- ISSN:
- 0364-9024
- Page Range / eLocation ID:
- p. 554-577
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract We used seismic refraction to image the P‐wave velocity structure of a shale watershed experiencing regional compression in the Valley and Ridge Province (USA). From estimates showing strong compressional stress, we expected the depth to unweathered bedrock to mirror the hill‐valley‐hill topography (“bowtie pattern”) by analogy to seismic velocity patterns in crystalline bedrock in the North American Piedmont that also experience compression. Previous researchers used failure potentials calculated for strong compression in the Piedmont to suggest fractures are open deeper under hills than valleys to explain the “bowtie” pattern. Seismic images of the shale watershed, however, show little evidence of such a “bowtie.” Instead, they are consistent with weak (not strong) compression. This contradiction could be explained by the greater importance of infiltration‐driven weathering than fracturing in determining seismic velocities in shale compared to crystalline bedrock, or to local perturbations of the regional stress field due to lithology or structures.more » « less
-
Abstract We present protocols to generate arbitrary photonic graph states from quantum emitters that are in principle deterministic. We focus primarily on two-dimensional cluster states of arbitrary size due to their importance for measurement-based quantum computing. Our protocols for these and many other types of two-dimensional graph states require a linear array of emitters in which each emitter can be controllably pumped, rotated about certain axes, and entangled with its nearest neighbors. We show that an error on one emitter produces a localized region of errors in the resulting graph state, where the size of the region is determined by the coordination number of the graph. We describe how these protocols can be implemented for different types of emitters, including trapped ions, quantum dots, and nitrogen-vacancy centers in diamond.more » « less
-
Abstract The classical Hadwiger conjecture dating back to 1940s states that any graph of chromatic number at leastrhas the clique of orderras a minor. Hadwiger's conjecture is an example of a well‐studied class of problems asking how large a clique minor one can guarantee in a graph with certain restrictions. One problem of this type asks what is the largest size of a clique minor in a graph onnvertices of independence numberat mostr. If true Hadwiger's conjecture would imply the existence of a clique minor of order. Results of Kühn and Osthus and Krivelevich and Sudakov imply that if one assumes in addition thatGisH‐free for some bipartite graphHthen one can find a polynomially larger clique minor. This has recently been extended to triangle‐free graphs by Dvořák and Yepremyan, answering a question of Norin. We complete the picture and show that the same is true for arbitrary graphH, answering a question of Dvořák and Yepremyan. In particular, we show that any‐free graph has a clique minor of order, for some constantdepending only ons. The exponent in this result is tight up to a constant factor in front of theterm.more » « less
-
Abstract We study viscosity solutions to the classical one-phase problem and its thin counterpart. In low dimensions, we show that when the free boundary is the graph of a continuous function, the solution is the half-plane solution. This answers, in the salient dimensions, a one-phase free boundary analogue of Bernstein’s problem for minimal surfaces.As an application, we also classify monotone solutions of semilinear equations with a bump-type nonlinearity.more » « less
