Abstract. Let [Formula: see text] be a graph, and let [Formula: see text] be a hereditary class of theta-free graphs such that [Formula: see text]. We prove that if (a) [Formula: see text] is a forest, and (b) [Formula: see text] excludes the line graphs of all subdivisions of some wall, then the treewidth of every graph in [Formula: see text] is at most a polynomial function of its clique number. This is best possible in that both (a) and (b) are necessary for the existence of any function with the above property.

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).

Abstract. The List-3-Coloring Problem is to decide, given a graph [Formula: see text] and a list [Formula: see text] of colors assigned to each vertex [Formula: see text] of [Formula: see text], whether [Formula: see text] admits a proper coloring [Formula: see text] with [Formula: see text] for every vertex [Formula: see text] of [Formula: see text], and the 3-Coloring Problem is the List-3-Coloring Problem on instances with [Formula: see text] for every vertex [Formula: see text] of [Formula: see text]. The List-3-Coloring Problem is a classical NP -complete problem, and it is well-known that while restricted to [Formula: see text]- free graphs (meaning graphs with no induced subgraph isomorphic to a fixed graph [Formula: see text]), it remains NP -complete unless [Formula: see text] is isomorphic to an induced subgraph of a path. However, the current state of art is far from proving this to be sufficient for a polynomial time algorithm; in fact, the complexity of the 3-Coloring Problem on [Formula: see text]-free graphs (where [Formula: see text] denotes the eight-vertex path) is unknown. Here we consider a variant of the List-3-Coloring Problem called the Ordered Graph List-3-Coloring Problem, where the input is an ordered graph, that is, a graph along with a linear order on its vertex set. For ordered graphs [Formula: see text] and [Formula: see text], we say [Formula: see text] is [Formula: see text]- free if [Formula: see text] is not isomorphic to an induced subgraph of [Formula: see text] with the isomorphism preserving the linear order. We prove, assuming [Formula: see text] to be an ordered graph, a nearly complete dichotomy for the Ordered Graph List-3-Coloring Problem restricted to [Formula: see text]-free ordered graphs. In particular, we show that the problem can be solved in polynomial time if [Formula: see text] has at most one edge, and remains NP -complete if [Formula: see text] has at least three edges. Moreover, in the case where [Formula: see text] has exactly two edges, we give a complete dichotomy when the two edges of [Formula: see text] share an end, and prove several NP -completeness results when the two edges of [Formula: see text] do not share an end, narrowing the open cases down to three very special types of two-edge ordered graphs.

For a positive integer $r$ and graphs $G$ and $H$, we denote by $G+H$ the disjoint union of $G$ and $H$ and by $rH$ the union of $r$ mutually disjoint copies of $H$. Also, we say $G$ is $H$ -free if $H$ is not isomorphic to an induced subgraph of $G$. We use $P_t$ to denote the path on $t$ vertices. For a fixed positive integer $k$, the List-$k$-Coloring Problem is to decide, given a graph $G$ and a list $L(v)\subseteq \{1,\ldots,k\}$ of colors assigned to each vertex $v$ of $G$, whether $G$ admits a proper coloring $\phi$ with $\phi(v)\in L(v)$ for every vertex $v$ of $G$, and the $k$-Coloring Problem is the List-$k$-Coloring Problem restricted to instances with $L(v)=\{1,\ldots, k\}$ for every vertex $v$ of $G$. We prove that, for every positive integer $r$, the List-$5$-Coloring Problem restricted to $rP_3$-free graphs can be solved in polynomial time. Together with known results, this gives a complete dichotomy for the complexity of the List-5-Coloring Problem restricted to $H$-free graphs: For every graph $H$, assuming P$\neq$NP, the List-5-Coloring Problem restricted to $H$-free graphs can be solved in polynomial time if and only if, $H$ is an induced subgraph of either $rP_3$ or $P_5+rP_1$ for some positive integer $r$. As a hardness counterpart, we also show that the $k$-Coloring Problem restricted to $rP_4$-free graphs is NP-complete for all $k\geq 5$ and $r\geq 2$.