Paweł Rafał Bieliński

Paweł Rafał Bieliński, Jadwiga Czyżewska, Martin Milanič et al.

A $P_4$ is a chordless path on four vertices. A diamond is a graph obtained from a clique of size four by removing one edge of the clique. A paw is a graph obtained from a clique of size four by removing two adjacent edges of the clique. We prove that for a graph $H$, the class of graphs with no induced subdivision of $H$ has bounded clique-width if and only if $H$ is an induced subgraph of $P_4$, the paw, or the diamond. This answers a~question of Dabrowski, Johnson, and Paulusma.

Paweł Rafał Bieliński, Marta Piecyk, Paweł Rzążewski

The complexity of classical computational problems in graph classes defined by forbidding induced subgraphs is one of the central topics of algorithmic graph theory. Recently, there has been a growing interest in the complexity of such problems in ordered graphs, i.e., graphs with a fixed linear ordering of vertices. Such an approach allows us to investigate the boundary of tractability more closely. However, most results so far concern coloring problems. In this paper, we focus on the complexity of the Maximum Weight Independent Set (MWIS) problem in classes of ordered graphs. For every ordered graph $H$, we classify the complexity of MWIS in ordered graphs that exclude $H$ as an induced subgraph into one of the following cases: (1) solvable in polynomial time, (2) solvable in quasipolynomial time, (3) solvable in subexponential time, (4) NP-hard. Notably, case (3) contains only one well-structured family of $H$ obtained from two nested edges by adding isolated vertices in a specific way. Thus, our results yield an almost complete complexity dichotomy for MWIS in classes of ordered graphs defined by a single forbidden induced subgraph into cases solvable in quasipolynomial time and those that are NP-hard.