An official website of the United States government
We prove that the tree independence number of every even-hole-free graph is at most polylogarithmic in its number of vertices. More explicitly, we prove that there exists a constant c > 0 such that for every integer n > 1 every n-vertex even-hole-free graph has a tree decomposition where each bag has stability (independence) number at most clog10 n. This implies that the Maximum Weight Independent Set problem, as well as several other natural algorithmic problems that are known to be NP-hard in general, can be solved in quasipolynomial time if the input graph is even-hole-free. The quasi-polynomial complexity will remain the same even if the exponent of the logarithm is reduced to 1 (which would be asymptotically best possible).
more »
« less
Rainbow even cycles
We prove that every family of (not necessarily distinct) even cycles D_1,...,D_{1.2n-1} on some fixed n-vertex set has a rainbow even cycle (that is, a set of edges from distinct D_i’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.
more »
« less
- Award ID(s):
- 2154063
- PAR ID:
- 10620690
- Publisher / Repository:
- SIAM
- Date Published:
- Journal Name:
- SIAM journal on discrete mathematics
- ISSN:
- 1095-7146
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
The following generalisation of the Erdős unit distance problem was recently suggested by Palsson, Senger and Sheffer. For a sequence δ=(δ₁,… ,δ_k) of k distances, a (k+1)-tuple (p₁,… ,p_{k+1}) of distinct points in ℝ^d is called a (k,δ)-chain if ‖p_j-p_{j+1}‖ = δ_j for every 1 ≤ j ≤ k. What is the maximum number C_k^d(n) of (k,δ)-chains in a set of n points in ℝ^d, where the maximum is taken over all δ? Improving the results of Palsson, Senger and Sheffer, we essentially determine this maximum for all k in the planar case. It is only for k ≡ 1 (mod 3) that the answer depends on the maximum number of unit distances in a set of n points. We also obtain almost sharp results for even k in dimension 3.more » « less
-
Abstract The Erdős–Hajnal conjecture says that for every graph there exists such that every graph not containing as an induced subgraph has a clique or stable set of cardinality at least . We prove that this is true when is a cycle of length five. We also prove several further results: for instance, that if is a cycle and is the complement of a forest, there exists such that every graph containing neither of as an induced subgraph has a clique or stable set of cardinality at least .more » « less
-
We develop a theory of linear isoperimetric inequalities for graphs on surfaces and apply it to coloring problems, as follows. Let $ G$ be a graph embedded in a fixed surface $$ \Sigma $$ of genus $ g$ and let $$ L=(L(v):v\in V(G))$$ be a collection of lists such that either each list has size at least five, or each list has size at least four and $ G$ is triangle-free, or each list has size at least three and $ G$ has no cycle of length four or less. An $ L$-coloring of $ G$ is a mapping $$ \phi $$ with domain $ V(G)$ such that $$ \phi (v)\in L(v)$$ for every $$ v\in V(G)$$ and $$ \phi (v)\ne \phi (u)$$ for every pair of adjacent vertices $$ u,v\in V(G)$$. We prove if every non-null-homotopic cycle in $ G$ has length $$ \Omega (\log g)$$, then $ G$ has an $ L$-coloring, if $ G$ does not have an $ L$-coloring, but every proper subgraph does (``$ L$-critical graph''), then $$ \vert V(G)\vert=O(g)$$, if every non-null-homotopic cycle in $ G$ has length $$ \Omega (g)$$, and a set $$ X\subseteq V(G)$$ of vertices that are pairwise at distance $$ \Omega (1)$$ is precolored from the corresponding lists, then the precoloring extends to an $ L$-coloring of $ G$, if every non-null-homotopic cycle in $ G$ has length $$ \Omega (g)$$, and the graph $ G$ is allowed to have crossings, but every two crossings are at distance $$ \Omega (1)$$, then $ G$ has an $ L$-coloring, if $ G$ has at least one $ L$-coloring, then it has at least $$ 2^{\Omega (\vert V(G)\vert)}$$ distinct $ L$-colorings. We show that the above assertions are consequences of certain isoperimetric inequalities satisfied by $ L$-critical graphs, and we study the structure of families of embedded graphs that satisfy those inequalities. It follows that the above assertions hold for other coloring problems, as long as the corresponding critical graphs satisfy the same inequalities.more » « less
-
Let ϕ(x) = xd + c be an integral polynomial of degree at least 2, and consider the sequence (ϕn(0))n=0∞, which is the orbit of 0 under iteration by ϕ. Let Dd,c denote the set of positive integers n for which n | ϕn(0). We give a characterization of Dd,c in terms of a directed graph and describe a number of its properties, including its cardinality and the primes contained therein. In particular, we study the question of which primes p have the property that the orbit of 0 is a single p-cycle modulo p. We show that the set of such primes is finite when d is even, and conjecture that it is infinite when d is odd.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- The DOI is not currently available.
