We show that given an n-vertex graph G of diameter 3 we can decide if G is 3-colourable in time 2^{O(n^{2/3-ε})} for any ε < 1/33. This improves on the previous best algorithm of 2^{O((nlog n)^{2/3})} from Dębski, Piecyk and Rzążewski [Faster 3-coloring of small-diameter graphs, ESA 2021].

Abstract. Given [Formula: see text] graphs [Formula: see text], their intersection is the graph [Formula: see text]. Given [Formula: see text] graph classes [Formula: see text], we call the class [Formula: see text] the graph-intersection of [Formula: see text]. The main motivation for the work presented in this paper is to try to understand under which conditions graph-intersection preserves [Formula: see text]-boundedness. We consider the following two questions: (1) Which graph classes have the property that their graph-intersection with every [Formula: see text] -bounded class of graphs is [Formula: see text] -bounded? We call such a class intersectionwise [Formula: see text] -guarding. We prove that classes of graphs which admit a certain kind of decomposition are intersectionwise [Formula: see text]-guarding. We provide necessary conditions that a finite set of graphs [Formula: see text] should satisfy if the class of [Formula: see text]-free graphs is intersectionwise [Formula: see text]-guarding, and we characterize the intersectionwise [Formula: see text]-guarding classes which are defined by a single forbidden induced subgraph. (2) Which graph classes have the property that, for every positive integer [Formula: see text] , their [Formula: see text] -fold graph-intersection is [Formula: see text] -bounded? We call such a class intersectionwise self-[Formula: see text] -guarding. We study intersectionwise self-[Formula: see text]-guarding classes which are defined by a single forbidden induced subgraph, and we prove a result which allows us to construct intersectionwise self-[Formula: see text]-guarding classes from known intersectionwise [Formula: see text]-guarding classes.

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. This is the first paper in a series whose goal is to give a polynomial-time algorithm for the 4-coloring problem and the 4-precoloring extension problem restricted to the class of graphs with no induced six-vertex path, thus proving a conjecture of Huang. Combined with previously known results, this completes the classification of the complexity of the 4-coloring problem for graphs with a connected forbidden induced subgraph. In this paper we give a polynomial-time algorithm that determines if a special kind of precoloring of a [Formula: see text]-free graph has a precoloring extension, and constructs such an extension if one exists. Combined with the main result of the second paper of the series, this gives a complete solution to the problem.

Abstract. This is the second paper in a series of two. The goal of the series is to give a polynomial-time algorithm for the 4-coloring problem and the 4-precoloring extension problem restricted to the class of graphs with no induced six-vertex path, thus proving a conjecture of Huang. Combined with previously known results, this completes the classification of the complexity of the 4-coloring problem for graphs with a connected forbidden induced subgraph. In this paper we give a polynomial time-algorithm that starts with a 4-precoloring of a graph with no induced six-vertex path and outputs a polynomial-sized collection of so-called excellent precolorings. Excellent precolorings are easier to handle than general ones, and, in addition, in order to determine whether the initial precoloring can be extended to the whole graph, it is enough to answer the same question for each of the excellent precolorings in the collection. The first paper in the series deals with excellent precolorings, thus providing a complete solution to the problem.

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.

Abstract. Fix [Formula: see text], and let [Formula: see text] be a graph, with vertex set partitioned into [Formula: see text] subsets (“blocks”) of approximately equal size. An induced subgraph of [Formula: see text] is “transversal” (with respect to this partition) if it has exactly one vertex in each block (and therefore it has exactly [Formula: see text] vertices). A “pure pair” in [Formula: see text] is a pair [Formula: see text] of disjoint subsets of [Formula: see text] such that either all edges between [Formula: see text] are present or none are; and in the present context we are interested in pure pairs [Formula: see text] where each of [Formula: see text] is a subset of one of the blocks, and not the same block. This paper collects several results and open questions concerning how large a pure pair must be present if various types of transversal subgraphs are excluded.

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

A pure pair in a graph $G$ is a pair $(Z_1,Z_2)$ of disjoint sets of vertices such that either every vertex in $Z_1$ is adjacent to every vertex in $Z_2$, or there are no edges between $Z_1$ and $Z_2$. With Maria Chudnovsky, we recently proved that, for every forest $F$, every graph $G$ with at least two vertices that does not contain $F$ or its complement as an induced subgraph has a pure pair $(Z_1,Z_2)$ with $|Z_1|,|Z_2|$ linear in $|G|$. Here we investigate what we can say about pure pairs in an ordered graph $G$, when we exclude an ordered forest $F$ and its complement as induced subgraphs. Fox showed that there need not be a linear pure pair; but Pach and Tomon showed that if $F$ is a monotone path, then there is a pure pair of size $c|G|/\log |G|$. We generalize this to all ordered forests, at the cost of a slightly worse bound: we prove that, for every ordered forest $F$, every ordered graph $G$ with at least two vertices that does not contain $F$ or its complement as an induced subgraph has a pure pair of size $|G|^{1-o(1)}$.

We study the Max Partial $H$-Coloring problem: given a graph $G$, find the largest induced subgraph of $G$ that admits a homomorphism into $H$, where $H$ is a fixed pattern graph without loops. Note that when $H$ is a complete graph on $k$ vertices, the problem reduces to finding the largest induced $k$-colorable subgraph, which for $k=2$ is equivalent (by complementation) to Odd Cycle Transversal. We prove that for every fixed pattern graph $H$ without loops, Max Partial $H$-Coloring can be solved in $\{P_5,F\}$-free graphs in polynomial time, whenever $F$ is a threshold graph; in $\{P_5,{bull}\}$-free graphs in polynomial time; in $P_5$-free graphs in time $n^{\mathcal{O}(\omega(G))}$; and in $\{P_6,{1-subdivided claw}\}$-free graphs in time $n^{\mathcal{O}(\omega(G)^3)}$. Here, $n$ is the number of vertices of the input graph $G$ and $\omega(G)$ is the maximum size of a clique in $G$. Furthermore, by combining the mentioned algorithms for $P_5$-free and for $\{P_6,{1-subdivided claw}\}$-free graphs with a simple branching procedure, we obtain subexponential-time algorithms for Max Partial $H$-Coloring in these classes of graphs. Finally, we show that even a restricted variant of Max Partial $H$-Coloring is $\mathsf{NP}$-hard in the considered subclasses of $P_5$-free graphs if we allow loops on $H$.

In the vector space of symmetric functions, the elements of the basis of elementary symmetric functions are (up to a factor) the chromatic symmetric functions of disjoint unions of cliques. We consider their graph complements, the functions $\{r_{\lambda}: \lambda \text{ an integer partition}\}$ defined as chromatic symmetric functions of complete multipartite graphs. This basis was first introduced by Penaguiao [ J. Combin. Theory Ser. A, 175 (2020), 105258]. We provide a combinatorial interpretation for the coefficients of the change-of-basis formula between the $r_{\lambda}$ and the monomial symmetric functions, and we show that the coefficients of the chromatic and Tutte symmetric functions of a graph $G$ when expanded in the $r$-basis enumerate certain intersections of partitions of $V(G)$.

We give a polynomial-time algorithm to test whether a graph contains an induced cycle with length more than three and odd.

For a graph F, a graph G is F-free if it does not contain an induced subgraph isomorphic to F. For two graphs G and H, an H-coloring of G is a mapping f:V(G) -> V(H) such that for every edge uv in E(G) it holds that f(u)f(v)in E(H). We are interested in the complexity of the problem H-Coloring, which asks for the existence of an H-coloring of an input graph G. In particular, we consider H-Coloring of F-free graphs, where F is a fixed graph and H is an odd cycle of length at least 5. This problem is closely related to the well known open problem of determining the complexity of 3-Coloring of P_t-free graphs. We show that for every odd k >= 5 the C_k-Coloring problem, even in the precoloring-extension variant, can be solved in polynomial time in P_9-free graphs. On the other hand, we prove that the extension version of C_k-Coloring is NP-complete for F-free graphs whenever some component of F is not a subgraph of a subdivided claw.

In this paper we present a polynomial time algorithm for the 4-COLORING PROBLEM and the 4-PRECOLORING EXTENSION problem restricted to the class of graphs with no induced six-vertex path, thus proving a conjecture of Huang. Combined with previously known results this completes the classification of the complexity of the 4-coloring problem for graphs with a connected forbidden induced subgraph.

We consider the problem of constructing fast and small binary adder circuits. Among widely used adders, the Kogge-Stone adder is often considered the fastest, because it computes the carry bits for two n -bit numbers (where n is a power of two) with a depth of 2 log 2 n logic gates, size 4 n log 2 n , and all fan-outs bounded by two. Fan-outs of more than two are disadvantageous in practice, because they lead to the insertion of repeaters for repowering the signal and additional depth in the physical implementation. However, the depth bound of the Kogge-Stone adder is off by a factor of two from the lower bound of log 2 n . Two separate constructions by Brent and Krapchenko achieve this lower bound asymptotically. Brent’s construction gives neither a bound on the fan-out nor the size, while Krapchenko’s adder has linear size, but can have up to linear fan-out. With a fan-out bound of two, neither construction achieves a depth of less than 2 log 2 n . In a further approach, Brent and Kung proposed an adder with linear size and fan-out two but twice the depth of the Kogge-Stone adder. These results are 33–43 years old and no substantial theoretical improvement for has been made since then. In this article, we integrate the individual advantages of all previous adder circuits into a new family of full adders, the first to improve on the depth bound of 2 log 2 n while maintaining a fan-out bound of two. Our adders achieve an asymptotically optimum logic gate depth of log 2 n + o (log 2 n ) and linear size O ( n ).

We study the minimum rectilinear Steiner tree problem in the presence of obstacles. Traversing obstacles is not strictly forbidden, but the total length of each connected component in the intersection of the tree with the interior of the blocked area is bounded by a constant.