An official website of the United States government
Abstract What are the unavoidable induced subgraphs of graphs with large treewidth? It is well‐known that the answer must include a complete graph, a complete bipartite graph, all subdivisions of a wall and line graphs of all subdivisions of a wall (we refer to these graphs as the “basic treewidth obstructions”). So it is natural to ask whether graphs excluding the basic treewidth obstructions as induced subgraphs have bounded treewidth. Sintiari and Trotignon answered this question in the negative. Their counterexamples, the so‐called “layered wheels,” contain wheels, where awheelconsists of ahole(i.e., an induced cycle of length at least four) along with a vertex with at least three neighbors in the hole. This leads one to ask whether graphs excluding wheels and the basic treewidth obstructions as induced subgraphs have bounded treewidth. This also turns out to be false due to Davies' recent example of graphs with large treewidth, no wheels and no basic treewidth obstructions as induced subgraphs. However, in Davies' example there exist holes and vertices (outside of the hole) with two neighbors in them. Here we prove that a hole with a vertex with at least two neighbors in it is inevitable in graphs with large treewidth and no basic obstruction. Our main result is that graphs in which every vertex has at most one neighbor in every hole (that does not contain it) and with the basic treewidth obstructions excluded as induced subgraphs have bounded treewidth.
more »
« less
Sharp lower bounds for the number of maximum matchings in bipartite multigraphs
Abstract We study the minimum number of maximum matchings in a bipartite multigraph with parts and under various conditions, refining the well‐known lower bound due to M. Hall. When , every vertex in has degree at least , and every vertex in has at least distinct neighbors, the minimum is when and is when . When every vertex has at least two neighbors and , the minimum is , where . We also determine the minimum number of maximum matchings in several other situations. We provide a variety of sharpness constructions.
more »
« less
- PAR ID:
- 10592093
- Publisher / Repository:
- Wiley
- Date Published:
- Journal Name:
- Journal of Graph Theory
- Volume:
- 106
- Issue:
- 3
- ISSN:
- 0364-9024
- Page Range / eLocation ID:
- 525 to 555
- Subject(s) / Keyword(s):
- Maximum matching counting.
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Let $$x,y\in (0,1]$$, and let $A,B,C$ be disjoint nonempty stable subsets of a graph $$G$$, where every vertex in $$A$$ has at least $x|B|$ neighbours in $$B$$, and every vertex in $$B$$ has at least $y|C|$ neighbours in $$C$$, and there are no edges between $A,C$. We denote by $$\phi(x,y)$$ the maximum $$z$$ such that, in all such graphs $$G$$, there is a vertex $$v\in C$$ that is joined to at least $z|A|$ vertices in $$A$$ by two-edge paths. This function has some interesting properties: we show, for instance, that $$\phi(x,y)=\phi(y,x)$$ for all $x,y$, and there is a discontinuity in $$\phi(x,x)$$ when $1/x$ is an integer. For $z=1/2, 2/3,1/3,3/4,2/5,3/5$, we try to find the (complicated) boundary between the set of pairs $(x,y)$ with $$\phi(x,y)\ge z$$ and the pairs with $$\phi(x,y)1/3$.more » « less
-
We consider the question of orienting the edges in a graph G such that every vertex has bounded out-degree. For graphs of arboricity α, there is an orientation in which every vertex has out-degree at most α and, moreover, the best possible maximum out-degree of an orientation is at least α - 1. We are thus interested in algorithms that can achieve a maximum out-degree of close to α. A widely studied approach for this problem in the distributed algorithms setting is a "peeling algorithm" that provides an orientation with maximum out-degree α(2+ε) in a logarithmic number of iterations. We consider this problem in the local computation algorithm (LCA) model, which quickly answers queries of the form "What is the orientation of edge (u,v)?" by probing the input graph. When the peeling algorithm is executed in the LCA setting by applying standard techniques, e.g., the Parnas-Ron paradigm, it requires Ω(n) probes per query on an n-vertex graph. In the case where G has unbounded degree, we show that any LCA that orients its edges to yield maximum out-degree r must use Ω(√ n/r) probes to G per query in the worst case, even if G is known to be a forest (that is, α = 1). We also show several algorithms with sublinear probe complexity when G has unbounded degree. When G is a tree such that the maximum degree Δ of G is bounded, we demonstrate an algorithm that uses Δ n^{1-log_Δ r + o(1)} probes to G per query. To obtain this result, we develop an edge-coloring approach that ultimately yields a graph-shattering-like result. We also use this shattering-like approach to demonstrate an LCA which 4-colors any tree using sublinear probes per query.more » « less
-
This paper considers the Byzantine consensus problem for nodes with binary inputs. The nodes are interconnected by a network represented as an undirected graph, and the system is assumed to be synchronous. Under the classical point-to-point communication model, it is well-known that the following two conditions are both necessary and sufficient to achieve Byzantine consensus among n nodes in the presence of up to ƒ Byzantine faulty nodes: n & 3 #8805; 3 ≥ ƒ+ 1 and vertex connectivity at least 2 ƒ + 1. In the classical point-to-point communication model, it is possible for a faulty node to equivocate, i.e., transmit conflicting information to different neighbors. Such equivocation is possible because messages sent by a node to one of its neighbors are not overheard by other neighbors. This paper considers the local broadcast model. In contrast to the point-to-point communication model, in the local broadcast model, messages sent by a node are received identically by all of its neighbors. Thus, under the local broadcast model, attempts by a node to send conflicting information can be detected by its neighbors. Under this model, we show that the following two conditions are both necessary and sufficient for Byzantine consensus: vertex connectivity at least ⌋ 3 fƒ / 2 ⌊ + 1 and minimum node degree at least 2 ƒ. Observe that the local broadcast model results in a lower requirement for connectivity and the number of nodes n, as compared to the point-to-point communication model. We extend the above results to a hybrid model that allows some of the Byzantine faulty nodes to equivocate. The hybrid model bridges the gap between the point-to-point and local broadcast models, and helps to precisely characterize the trade-off between equivocation and network requirements.more » « less
-
Abstract We prove that the number of edges of a multigraph with vertices is at most , provided that any two edges cross at most once, parallel edges are noncrossing, and the lens enclosed by every pair of parallel edges in contains at least one vertex. As a consequence, we prove the following extension of the Crossing Lemma of Ajtai, Chvátal, Newborn, Szemerédi, and Leighton, if has edges, in any drawing of with the above property, the number of crossings is . This answers a question of Kaufmann et al. and is tight up to the logarithmic factor.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1002/jgt.23080
