An apple A_{k} is a graph obtained from a chordless cycle C_{k} of length k ≥ 4 by adding a vertex that has exactly one neighbor on the cycle. A graph is *apple-free* if it contains no A_{k}, k ≥ 4, as an induced subgraph. Since every apple contains an induced claw, a chordless cycle of length at least four, and an induced path on four vertices, the class of apple-free graphs generalizes that of claw-free graphs, chordal graphs, and cographs. In this work, we provide an explicit description of the structure of all apple-free graphs.

This paper is motivated by the following question: what are the unavoidable induced subgraphs of graphs with large treewidth? Aboulker et al. made a conjecture which answers this question in graphs of bounded maximum degree, asserting that for all k and ∆, every graph with maximum degree at most ∆ and sufficiently large treewidth contains either a subdivision of the (k × k)-wall or the line graph of a subdivision of the (k × k)-wall as an induced subgraph. We prove two theorems supporting this conjecture, as follows.

1. For t ≥ 2, a t-theta is a graph consisting of two nonadjacent vertices and three internally disjoint paths between them, each of length at least t. A t-pyramid is a graph consisting of a vertex v, a triangle B disjoint from v and three paths starting at v and disjoint otherwise, each joining v to a vertex of B, and each of length at least t. We prove that for all k, t and ∆, every graph with maximum degree at most ∆ and sufficiently large treewidth contains either a t-theta, or a t-pyramid, or the line graph of a subdivision of the (k ×k)-wall as an induced subgraph. This affirmatively answers a question of Pilipczuk et al. asking whether every graph of bounded maximum degree and sufficiently large treewidth contains either a theta or a triangle as an induced subgraph (where a theta means a t-theta for some t ≥ 2).

2. A subcubic subdivided caterpillar is a tree of maximum degree at most three whose all vertices of degree three lie on a path. We prove that for every ∆ and subcubic subdivided caterpillar T, every graph with maximum degree at most ∆ and sufficiently large treewidth contains either a subdivision of T or the line graph of a subdivision of T as an induced subgraph.

%G eng %U https://arxiv.org/abs/2108.01162 %0 Journal Article %D Submitted %T Submodular functions and perfect graphs %A Tara Abrishami %A Maria Chudnovsky %A Cemil Dibek %A Kristina Vušković %X We give a combinatorial polynomial-time algorithm to find a maximum weight independent set in perfect graphs of bounded degree that do not contain a prism or a hole of length four as an induced subgraph. An *even pair* in a graph is a pair of vertices all induced paths between which are even. An *even set* is a set of vertices every two of which are an even pair. We show that every perfect graph that does not contain a prism or a hole of length four as an induced subgraph has a balanced separator which is the union of a bounded number of even sets, where the bound depends only on the maximum degree of the graph. This allows us to solve the maximum weight independent set problem using the well-known submodular function minimization algorithm.

We present an algebraic characterization of perfect graphs, i.e., graphs for which the clique number and the chromatic number coincide for every induced subgraph. We show that a graph is perfect if and only if certain nonnegative polynomials associated with the graph are sums of squares. As a byproduct, we obtain several infinite families of nonnegative polynomials that are not sums of squares through graph-theoretic constructions. We also characterize graphs for which the associated polynomials belong to certain structured subsets of sum of squares polynomials. Finally, we reformulate some well-known results from the theory of perfect graphs as statements about sum of squares proofs of nonnegativity of certain polynomials.

%G eng %U https://arxiv.org/abs/2110.08950 %0 Journal Article %J Mathematics of Operations Research %D Forthcoming %T Sums of separable and quadratic polynomials %A Amir Ali Ahmadi %A Cemil Dibek %A Georgina Hall %X We study *separable plus quadratic* (SPQ) polynomials, i.e., polynomials that are the sum of univariate polynomials in different variables and a quadratic polynomial. Motivated by the fact that nonnegative separable and nonnegative quadratic polynomials are sums of squares, we study whether nonnegative SPQ polynomials are (i) the sum of a nonnegative separable and a nonnegative quadratic polynomial, and (ii) a sum of squares. We establish that the answer to question (i) is positive for univariate plus quadratic polynomials and for convex SPQ polynomials, but negative already for bivariate quartic SPQ polynomials. We use our decomposition result for convex SPQ polynomials to show that convex SPQ polynomial optimization problems can be solved by "small" semidefinite programs. For question (ii), we provide a complete characterization of the answer based on the degree and the number of variables of the SPQ polynomial. We also prove that testing nonnegativity of SPQ polynomials is NP-hard when the degree is at least four. We end by presenting applications of SPQ polynomials to upper bounding sparsity of solutions to linear programs, polynomial regression problems in statistics, and a generalization of Newton's method which incorporates separable higher-order derivative information.

For graphs G and H, we say that G is H-free if it does not contain H as an induced subgraph. Already in the early 1980s Alekseev observed that if H is connected, then the Max Weight Independent Set problem (MWIS) remains NP-hard in H-free graphs, unless H is a path or a subdivided claw, i.e., a graph obtained from the three-leaf star by subdividing each edge some number of times (possibly 0). Since then determining the complexity of MWIS in these remaining cases is one of the most important problems in algorithmic graph theory.

A general belief is that the problem is polynomial-time solvable, which is witnessed by algorithmic results for graphs excluding some small paths or subdivided claws. A more conclusive evidence was given by the recent breakthrough result by Gartland and Lokshtanov [FOCS 2020]: They proved that MWIS can be solved in quasipolynomial time in H-free graphs, where H is any fixed path. If H is an arbitrary subdivided claw, we know much less: The problem admits a QPTAS and a subexponential-time algorithm [Chudnovsky et al., SODA 2019].

In this paper we make an important step towards solving the problem by showing that for any subdivided claw H, MWIS is polynomial-time solvable in H-free graphs of bounded degree.

%B ACM-SIAM Symposium on Discrete Algorithms (SODA 2022) %G eng %U https://arxiv.org/pdf/2107.05434.pdf %0 Journal Article %J Journal of Combinatorial Theory, Series B %D 2022 %T Graphs with polynomially many minimal separators %A Tara Abrishami %A Maria Chudnovsky %A Cemil Dibek %A Stéphan Thomassé %A Nicolas Trotignon %A Kristina Vušković %XWe show that graphs that do not contain a theta, pyramid, prism, or turtle as an induced subgraph have polynomially many minimal separators. This result is the best possible in the sense that there are graphs with exponentially many minimal separators if only three of the four induced subgraphs are excluded. As a consequence, there is a polynomial time algorithm to solve the maximum weight independent set problem for the class of (theta, pyramid, prism, turtle)-free graphs. Since every prism, theta, and turtle contains an even hole, this also implies a polynomial time algorithm to solve the maximum weight independent set problem for the class of (pyramid, even hole)-free graphs.

%B Journal of Combinatorial Theory, Series B %V 152 %P 248-280 %G eng %U https://arxiv.org/abs/2005.05042 %0 Journal Article %J Discrete Mathematics %D 2021 %T New examples of minimal non-strongly-perfect graphs. %A Maria Chudnovsky %A Cemil Dibek %A Paul Seymour %X A graph is strongly perfect if every induced subgraph H has a stable set that meets every nonempty maximal clique of H. The characterization of strongly perfect graphs by a set of forbidden induced subgraphs is not known. Here we provide several new minimal non-strongly-perfect graphs. %B Discrete Mathematics %V 344 %G eng %U https://arxiv.org/abs/2003.01846 %N 5 %0 Journal Article %J Journal of Graph Theory %D 2021 %T Strongly perfect claw-free graphs - a short proof. %A Maria Chudnovsky %A Cemil Dibek %X A graph is strongly perfect if every induced subgraph H has a stable set that meets every maximal clique of H. A graph is claw-free if no vertex has three pairwise non-adjacent neighbors. The characterization of claw-free graphs that are strongly perfect by a set of forbidden induced subgraphs was conjectured by Ravindra in 1990 and was proved by Wang in 2006. Here we give a shorter proof of this characterization. %B Journal of Graph Theory %V 97 %P 359-381 %G eng %U https://arxiv.org/abs/1912.05645 %N 3 %0 Journal Article %J Discrete Mathematics %D 2017 %T Maximum number of edges in claw-free graphs whose maximum degree and matching number are bounded. %A C. Dibek %A T. Ekim %A P. Heggernes %X We determine the maximum number of edges that a claw-free graph can have, when its maximum degree and matching number are bounded. This is a famous problem that has been studied on general graphs, and for which there is a tight bound. The graphs achieving this bound contain in most cases an induced copy of K