Search

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 FROM AUTHOR]

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 P6-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 FROM AUTHOR]

The List-3-Coloring Problem is to decide, given a graph G and a list L(v) \subseteq \{ 1, 2, 3\} 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 3-Coloring Problem is the List-3-Coloring Problem on instances with L(v) =\{ 1, 2, 3\} for every vertex v of G. The List-3-Coloring Problem is a classical NP-complete problem, and it is well-known that while restricted to H-free graphs (meaning graphs with no induced subgraph isomorphic to a fixed graph H), it remains NP-complete unless H 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 P8-free graphs (where P8 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 G and H, we say G is H-free if H is not isomorphic to an induced subgraph of G with the isomorphism preserving the linear order. We prove, assuming H to be an ordered graph, a nearly complete dichotomy for the Ordered Graph List-3-Coloring Problem restricted to H-free ordered graphs. In particular, we show that the problem can be solved in polynomial time if H has at most one edge, and remains NP-complete if H has at least three edges. Moreover, in the case where H has exactly two edges, we give a complete dichotomy when the two edges of H share an end, and prove several NP-completeness results when the two edges of H do not share an end, narrowing the open cases down to three very special types of two-edge ordered graphs. [ABSTRACT FROM AUTHOR]

Fix k > 0, and let G be a graph, with vertex set partitioned into k subsets ("blocks") of approximately equal size. An induced subgraph of G is "transversal" (with respect to this partition) if it has exactly one vertex in each block (and therefore it has exactly k vertices). A "pure pair" in G is a pair X,Y of disjoint subsets of V (G) such that either all edges between X,Y are present or none are; and in the present context we are interested in pure pairs (X,Y) where each of X,Y 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. [ABSTRACT FROM AUTHOR]

A pure pair in a graph G is a pair (Z1,Z2) of disjoint sets of vertices such that either every vertex in Z1 is adjacent to every vertex in Z2, or there are no edges between Z1 and Z2. 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 (Z1,Z2) with | Z1|, | Z2| 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). [ABSTRACT FROM AUTHOR]

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 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). [ABSTRACT FROM AUTHOR]

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$. [ABSTRACT FROM AUTHOR]