Browsing Combinatorics and Optimization by Type "Article"
Now showing items 41-52 of 52
-
Pure pairs. II. Excluding all subdivisions of a graph
(Springer Nature, 2021-06-01)We prove for every graph H there exists ɛ > 0 such that, for every graph G with |G|≥2, if no induced subgraph of G is a subdivision of H, then either some vertex of G has at least ɛ|G| neighbours, or there are two disjoint ... -
Pure pairs. III. Sparse graphs with no polynomial-sized anticomplete pairs
(Wiley, 2020-11)A graph is H-free if it has no induced subgraph isomorphic to H, and |G| denotes the number of vertices of G. A conjecture of Conlon, Sudakov and the second author asserts that: - For every graph H, there exists ∈ > 0 ... -
Ramsey-nice families of graphs
(Elsevier, 2018-08)For a finite family $\cF$ of fixed graphs let $R_k(\cF)$ be the smallest integer $n$ for which every $k$-coloring of the edges of the complete graph $K_n$ yields a monochromatic copy of some $F\in\cF$. We say that $\cF$ ... -
Sandwich and probe problems for excluding paths
(Elsevier, 2018-12-31)Let Pk denote an induced path on k vertices. For k ≥ 5, we show that the Pk-free sandwich problem, partitioned probe problem, and unpartitioned probe problem are NP-complete. For k ≤ 4, it is known that the Pk-free sandwich ... -
The Sandwich Problem for Decompositions and Almost Monotone Properties
(Springer Nature, 2018)We consider the graph sandwich problem and introduce almost monotone properties, for which the sandwich problem can be reduced to the recognition problem. We show that the property of containing a graph in C as an induced ... -
Short Directed Cycles in Bipartite Digraphs
(Springer Nature, 2020-08-01)The Caccetta-Häggkvist conjecture implies that for every integer k ≥ 1, if G is a bipartite digraph, with n vertices in each part, and every vertex has out-degree more than n/(k+1), then G has a directed cycle of length ... -
Spectral properties of tensor products of channels
(Elsevier, 2018-09-15)We investigate spectral properties of the tensor products of two completely positive and trace preserving linear maps (also known as quantum channels) acting on matrix algebras. This leads to an important question of when ... -
A Stability Theorem for Matchings in Tripartite 3-Graphs
(Cambridge University Press, 2018-04-02)It follows from known results that every regular tripartite hypergraph of positive degree, with n vertices in each class, has matching number at least n/2. This bound is best possible, and the extremal configuration is ... -
Towards Erdős-Hajnal for Graphs with No 5-Hole
(Springer Nature, 2019-11-01)The Erdős-Hajnal conjecture says that for every graph H there exists c > 0 such that max(α(G), w(G)) ≥ nc for every H-free graph G with n vertices, and this is still open when H = C5. Until now the best bound known on ... -
Triangle-free graphs that do not contain an induced subdivision of K4 are 3-colorable
(Wiley, 2019-10)We show that triangle-free graphs that do not contain an induced subgraph isomorphic to a subdivision of K4 are 3-colorable. This proves a conjecture of Trotignon and Vušković. -
Triangle-free graphs with no six-vertex induced path
(Elsevier, 2018-08)The graphs with no five-vertex induced path are still not understood. But in the triangle-free case, we can do this and one better; we give an explicit construction for all triangle-free graphs with no six-vertex induced ... -
A Vertex-Weighted Tutte Symmetric Function, and Constructing Graphs with Equal Chromatic Symmetric Function
(The Electronic Journal of Combinatorics, 2021-04-09)This paper has two main parts. First, we consider the Tutte symmetric function XB, a generalization of the chromatic symmetric function. We introduce a vertex-weighted version ofXB, show that this function admits a ...