A Survey on the Computational Complexity of Colouring Graphs with Forbidden Subgraphs
---
paper_title: Polynomial Algorithms for Perfect Graphs

paper_content:

We show that the weighted versions of the stable set problem, the clique problem, the coloring problem and the clique covering problem are solvable in polynomial time for perfect graphs. Our algorithms are based on the ellipsoid method and a polynomial time separation algorithm for a certain class of positive semidefinite matrices related to Lovasz's bound θ( G ) on the Shannon capacity of a graph. We show that θ G ) can be computed in polynomial time for all graphs G and also give a new characterization of perfect graphs in terms of this number θ( G ). In addition we prove that the problem of verifying that a graph is imperfect is in NP. Moreover, we show that the computation of the stability number and the fractional stability number of a graph are unrelated with respect to hardness (if P ≠ NP ).
---
paper_title: Graph coloring problems

paper_content:

Planar Graphs. Graphs on Higher Surfaces. Degrees. Critical Graphs. The Conjectures of Hadwiger and Hajos. Sparse Graphs. Perfect Graphs. Geometric and Combinatorial Graphs. Algorithms. Constructions. Edge Colorings. Orientations and Flows. Chromatic Polynomials. Hypergraphs. Infinite Chromatic Graphs. Miscellaneous Problems. Indexes.
---
paper_title: Some simplified NP-complete graph problems

paper_content:

Abstract It is widely believed that showing a problem to be NP -complete is tantamount to proving its computational intractability. In this paper we show that a number of NP -complete problems remain NP -complete even when their domains are substantially restricted. First we show the completeness of Simple Max Cut (Max Cut with edge weights restricted to value 1), and, as a corollary, the completeness of the Optimal Linear Arrangement problem. We then show that even if the domains of the Node Cover and Directed Hamiltonian Path problems are restricted to planar graphs, the two problems remain NP -complete, and that these and other graph problems remain NP -complete even when their domains are restricted to graphs with low node degrees. For Graph 3-Colorability, Node Cover, and Undirected Hamiltonian Circuit, we determine essentially the lowest possible upper bounds on node degree for which the problems remain NP -complete.
---
paper_title: Coloring the vertices of a graph in prescribed colors

paper_content:

A lubricating composition comprises a lubricating oil which constitutes at least 85 per cent of the final composition, having a viscosity ranging from 5000 to 8000 S.S.U. at 0 DEG F., a viscosity index of 85 to 120, and a boiling range of not more than a 50 DEG F. difference between the 10 per cent and 90 per cent boiling points as determined by the ASTMD 1160 procedure at a pressure of 1 mm. of mercury, a first additive consisting of 1.5 to 5 per cent by volume but at least sufficient to increase the viscosity of the final lubricant composition to 60 to 70 S.S.U. at 210 DEG F. as measured by ASTM Test Procedure D88-44, of an oil-soluble methacrylic acid ester polymer having a molecular weight between 10,000 and 5,000,000 as determined by light scattering measurements, and a second additive comprising an alkaline earth metal glyoxide-alkaline earth metal sulphonate consisting of a dispersion of the reaction product of an alkylene glycol of less than 5 carbon atoms and an alkaline earth metal oxide or hydroxide dispersed in oil with the oil-soluble alkaline earth metal sulphonate. In the dispersion the ratio of metal as dispersed metal base (glycol reaction product) to metal as sulphonate dispersant ranges from 0.50:1 to 10:1, and in the final lubricant composition the amount of total metal, both dispersed metal base (glycoxide reaction product) and metal sulphonate dispersant, being from 20 to 120 millimols. per kilogram of the composition. The composition may also contain an oil-soluble salt of a thiophosphoric acid ester, a sulphur-containing inhibitor, a carboxylic acid as a viscosity modifier, and also extreme pressure agents, blooming agents, foam inhibitors, dyes and pour point modifiers. The glycoxide-sulphonate material can be formed in situ in the oil, e.g. by mixing the lubricating oil, ethylene glycol, an oil-soluble alkaline earth metal sulphonate, e.g. calcium petroleum mahogany sulphonate, and an alkaline earth metal oxide or hydroxide such as calcium or barium oxide, applying sufficient heat to effect reaction between the metal base and the ethylene glycol and removing uncombined glycol. The polymers may be those obtained from methacrylic acid esterified with alcohols such as hexyl, octyl, lauryl, cetyl, or octadecyl, or mixtures of these alcohols, e.g. those obtained from coconut oil. The thiophosphoric acid ester salt may contain metals such as calcium, barium or zinc. Specified thiophosphates are the zinc salts of butyl hexyl, methyl hexyl, butyl methyl-isobutylcarbinol, dioctyl, dihexadecyl, dibutylphenyl and dicetylphenyl dithiophosphoric acid. Suitable sulphur-containing inhibitors are dihexadecyl tetrasulphide, the reaction product of polychlorinated wax and sodium polysulphide, sulphurized terpenes, and the reaction products of terpenes and phosphorous sulphides. Specified carboxylic acid viscosity modifiers are formic, carbonic, lactic acid and mixtures.ALSO:A lubricating composition comprises a hydrocarbon lubricating oil which constitutes at least 85 per cent of the final composition, having a viscosity ranging from 5,000 to 8,000 S.S.U. at 0 DEG F., a viscosity index of 85 to 120, and a boiling range of not more than a 50 DEG F. difference between the 10 per cent and 90 per cent boiling points as determined by the ASTM/D1160 procedure at a pressure of 1 mm. of mercury, a first additive consisting of 1.5 to 5 per cent by volume but at least sufficient to increase the viscosity of the final lubricant composition to 60 to 70 S.S.U. at 210 DEG F. as measured by ASTM Test Procedure D88-44, of an oil-soluble methacrylic acid ester polymer having a molecular weight between 10,000 and 5,000,000 as determined by light scattering measurements, and a second additive comprising an alkaline earth metal glycoxide-alkaline earth metal sulphonate consisting of a dispersion of the reaction product of an alkylene glycol of less than 5 carbon atoms and an alkaline earth metal oxide or hydroxide dispersed in oil with the oil-soluble alkaline earth metal sulphonate. In the dispersion the ratio of metal as dispersed metal base-(glycol reaction product) to metal as sulphonate dispersant ranges from 0.50:1 to 10:1, and in the final lubricant composition the amount of total metal, both dispersed metal base (glycoxide reaction product) and metal sulphonate dispersant, being from 20 to 120 millimols per kilogram of the composition. The composition may also contain an oil-soluble salt of a thiophosphoric acid ester, a sulphur-containing inhibitor, a carboxylic acid as a viscosity modifier, and also extreme pressure agents, blooming agents, foam inhibitors, dyes and pour point modifiers. The glycoxide-sulphonate material can be formed in situ in the oil, e.g. by mixing the lubricating oil (for example mineral lubricating oil), ethylene glycol, an oil-soluble alkaline earth metal sulphonate, e.g. calcium petroleum mahogany sulphonate, and an alkaline earth metal oxide or hydroxide such as calcium or barium oxide, applying sufficient heat to effect reaction between the metal base and the ethylene glycol and removing uncombined glycol. The polymers may be those obtained from methacrylic acid esterified with alcohols such as hexyl, octyl, lauryl, cetyl, or octadecyl, or mixtures of these alcohols, e.g. those obtained from coconut oil. The thiophosphoric acid ester salt may contain metals such as calcium, barium or zinc. Specified thiophosphates are the zinc salts of butyl hexyl, methyl hexyl, butyl methyl-isobutylcarbinol, dioctyl, dihexadecyl, dibutylphenyl, and diacetylphenyl dithiophosphoric acid. Suitable sulphur-containing inhibitors are dihexadecyl tetrasulphide, the reaction product of polychlorinated wax and sodium polysulphide, sulphurized terpenes, and the reaction products of terpenes and phosphorus sulphides. Specified carboxylic acid viscosity modifiers are formic, carbonic, and lactic acids and mixtures thereof.
---
paper_title: A New Algorithm for Generating All the Maximal Independent Sets

paper_content:

The problem of generating all the maximal independent sets (or maximal cliques) of a given graph is fundamental in graph theory and is also one of the most important in terms of the application of graph theory. In this paper, we present a new efficient algorithm for generating all the maximal independent sets, for which processing time and memory space are bounded by $O(nm\mu)$ and $O(n+m)$, respectively, where n, m, and $\mu$ are the numbers of vertices, edges, and maximal independent sets of a graph.
---
paper_title: Generalized coloring for tree-like graphs

paper_content:

We discuss the Precoloring Extension (PrExt) and the List Coloring (LiCol) problems for trees, partial k-trees and cographs in the decision and the construction versions. Both problems for partial k-trees are solved in linear time, when the number of colors is a constant and by O(¦V¦k+2)-algorithmsin general. For trees, we improve this to linear time. In contrast to that, PrExt and LiCol differ in complexity for cographs. While the first has a linear algorithm, the second is shown NP-complete. We give polynomial algorithms for the corresponding enumeration problems #PrExt and #LiCol on partial k-trees and trees and for #PrExt on cographs.
---
paper_title: NP completeness of finding the chromatic index of regular graphs

paper_content:

Abstract We show that it is NP complete to determine whether it is possible to edge color a regular graph of degree k with k colors for any k ⩾ 3. As a by-product of this result, we obtain a new way to generate k -regular graphs which are k -edge colorable.
---
paper_title: Complexity of Coloring Graphs without Forbidden Induced Subgraphs

paper_content:

We give a complete characterization of parameter graphs H for which the problem of coloring H-free graphs is polynomial and for which it is NP-complete. We further initiate a study of this problem for two forbidden subgraphs.
---
paper_title: Colouring vertices of triangle-free graphs without forests

paper_content:

The vertex colouring problem is known to be NP-complete in the class of triangle-free graphs. Moreover, it is NP-complete in any subclass of triangle-free graphs defined by a finite collection of forbidden induced subgraphs, each of which contains a cycle. In this paper, we study the vertex colouring problem in subclasses of triangle-free graphs obtained by forbidding graphs without cycles, i.e., forests, and prove polynomial-time solvability of the problem in many classes of this type. In particular, our paper, combined with some previously known results, provides a complete description of the complexity status of the problem in subclasses of triangle-free graphs obtained by forbidding a forest with at most 6 vertices.
---
paper_title: Closing Complexity Gaps for Coloring Problems on H-Free Graphs

paper_content:

If a graph G contains no subgraph isomorphic to some graph H, then G is called H-free. A coloring of a graph G = (V,E) is a mapping c: V → {1,2,…} such that no two adjacent vertices have the same color, i.e., c(u) ≠ c(v) if uv ∈ E; if |c(V)| ≤ k then c is a k-coloring. The Coloring problem is to test whether a graph has a coloring with at most k colors for some integer k. The Precoloring Extension problem is to decide whether a partial k-coloring of a graph can be extended to a k-coloring of the whole graph for some integer k. The List Coloring problem is to decide whether a graph allows a coloring, such that every vertex u receives a color from some given set L(u). By imposing an upper bound l on the size of each L(u) we obtain the l-List Coloring problem. We first classify the Precoloring Extension problem and the l-List Coloring problem for H-free graphs. We then show that 3-List Coloring is NP-complete for n-vertex graphs of minimum degree n − 2, i.e., for complete graphs minus a matching, whereas List Coloring is fixed-parameter tractable for this graph class when parameterized by the number of vertices of degree n − 2. Finally, for a fixed integer k > 0, the List k -Coloring problem is to decide whether a graph allows a coloring, such that every vertex u receives a color from some given set L(u) that must be a subset of {1,…,k}. We show that List 4-Coloring is NP-complete for P 6-free graphs, where P 6 is the path on six vertices. This completes the classification of List k -Coloring for P 6-free graphs.
---
paper_title: Precoloring extension. III. Classes of perfect graphs

paper_content:

We continue the study of the following general problem on the vertex colourings of graphs. Suppose that some vertices of a graph G are assigned to some colours. Can this ‘precolouring’ be extended to a proper colouring of G with at most k colours (for some given k )? Here we investigate the complexity status of precolouring extendibility on some classes of perfect graphs, giving good characterizations (necessary and sufficient conditions) that lead to algorithms with linear or polynomial running time. It is also shown how a larger subclass of perfect graphs can be derived from graphs containing no induced path on four vertices.
---
paper_title: Three-coloring graphs with no induced seven-vertex path I : the triangle-free case

paper_content:

In this paper, we give a polynomial time algorithm which determines if a given triangle-free graph with no induced seven-vertex path is 3-colorable, and gives an explicit coloring if one exists.
---
paper_title: 4-coloring H-free graphs when H is small

paper_content:

The k-Coloring problem is to test whether a graph can be colored with at most k colors such that no two adjacent vertices receive the same color. If a graph G does not contain a graph H as an induced subgraph, then G is called H-free. For any fixed graph H on at most six vertices, it is known that 3-Coloring is polynomial-time solvable on H-free graphs whenever H is a linear forest, and NP-complete otherwise. By solving the missing case P"2+P"3, we prove the same result for 4-Coloring provided that H is a fixed graph on at most five vertices.
---
paper_title: On the complexity of 4-coloring graphs without long induced paths

paper_content:

We show that deciding if a graph without induced paths on nine vertices can be colored with 4 colors is an NP-complete problem, improving a previous NP-completeness result proved by Woeginger and Sgall in 2001. The complexity of 4-coloring graphs without induced paths on five vertices remains open. We show that deciding if a graph without induced paths or cycles on five vertices can be colored with 4 colors can be done in polynomial time. A step in our algorithm uses the well-known and deep fact due to Grotschel, Lovasz and Schrijver stating that perfect graphs can be optimally colored in polynomial time.
---
paper_title: Generalized coloring for tree-like graphs

paper_content:

We discuss the Precoloring Extension (PrExt) and the List Coloring (LiCol) problems for trees, partial k-trees and cographs in the decision and the construction versions. Both problems for partial k-trees are solved in linear time, when the number of colors is a constant and by O(¦V¦k+2)-algorithmsin general. For trees, we improve this to linear time. In contrast to that, PrExt and LiCol differ in complexity for cographs. While the first has a linear algorithm, the second is shown NP-complete. We give polynomial algorithms for the corresponding enumeration problems #PrExt and #LiCol on partial k-trees and trees and for #PrExt on cographs.
---
paper_title: Invitation to fixed-parameter algorithms

paper_content:

PART I: FOUNDATIONS 1. Introduction to Fixed-Parameter Algorithms 2. Preliminaries and Agreements 3. Parameterized Complexity Theory - A Primer 4. Vertex Cover - An Illustrative Example 5. The Art of Problem Parameterization 6. Summary and Concluding Remarks PART II: ALGORITHMIC METHODS 7. Data Reduction and Problem Kernels 8. Depth-Bounded Search Trees 9. Dynamic Programming 10. Tree Decompositions of Graphs 11. Further Advanced Techniques 12. Summary and Concluding Remarks PART III: SOME THEORY, SOME CASE STUDIES 13. Parameterized Complexity Theory 14. Connections to Approximation Algorithms 15. Selected Case Studies 16. Zukunftsmusik References Index
---
paper_title: Updating the complexity status of coloring graphs without a fixed induced linear forest

paper_content:

A graph is H-free if it does not contain an induced subgraph isomorphic to the graph H. The graph P"k denotes a path on k vertices. The @?-Coloring problem is the problem to decide whether a graph can be colored with at most @? colors such that adjacent vertices receive different colors. We show that 4-Coloring is NP-complete for P"8-free graphs. This improves a result of Le, Randerath, and Schiermeyer, who showed that 4-Coloring is NP-complete for P"9-free graphs, and a result of Woeginger and Sgall, who showed that 5-Coloring is NP-complete for P"8-free graphs. Additionally, we prove that the precoloring extension version of 4-Coloring is NP-complete for P"7-free graphs, but that the precoloring extension version of 3-Coloring can be solved in polynomial time for (P"2+P"4)-free graphs, a subclass of P"7-free graphs. Here P"2+P"4 denotes the disjoint union of a P"2 and a P"4. We denote the disjoint union of s copies of a P"3 by sP"3 and involve Ramsey numbers to prove that the precoloring extension version of 3-Coloring can be solved in polynomial time for sP"3-free graphs for any fixed s. Combining our last two results with known results yields a complete complexity classification of (precoloring extension of) 3-Coloring for H-free graphs when H is a fixed graph on at most 6 vertices: the problem is polynomial-time solvable if H is a linear forest; otherwise it is NP-complete.
---
paper_title: Three-coloring graphs with no induced seven-vertex path II : using a triangle

paper_content:

In this paper, we give a polynomial time algorithm which determines if a given graph containing a triangle and no induced seven-vertex path is 3-colorable, and gives an explicit coloring if one exists. In previous work, we gave a polynomial time algorithm for three-coloring triangle-free graphs with no induced seven-vertex path. Combined, our work shows that three-coloring a graph with no induced seven-vertex path can be done in polynomial time.
---
paper_title: The complexity of coloring graphs without long induced paths

paper_content:

We discuss the computational complexity of determining the chromatic number of graphs without long induced paths. We prove NP-completeness of deciding whether a Ps-free graph is 5-colorable and of deciding whether a Pi2-free graph is 4-colorable. Moreover, we give a polynomial time algorithm for deciding whether a Ps-free graph is 3-colorable.
---
paper_title: Three-colourability and forbidden subgraphs. II: polynomial algorithms

paper_content:

In this paper we study the chromatic number for graphs with forbidden induced subgraphs. We focus our interest on graph classes (defined in terms of forbidden induced subgraphs) for which the question of 3-colourability can be decided in polynomial time and, if so, a proper 3-colouring can be determined also in polynomial time. Note that the 3-colourability decision problem is a well-known NP-complete problem, even for special graph classes, e.g. triangle-free and K1,5-free (Discrete Math. 162 (1-3) (1996) 313). Therefore, it is unlikely that there exists a polynomial algorithm deciding whether there exists a 3-colouring of a given graph in general. We present three different approaches to reach our goal. The first approach is purely a structural analysis of the graph class in consideration; the second one is a structural analysis of only the non-perfect K4-free members of the considered graph class; finally the last approach is based on propositional logic and bounded dominating subgraphs.
---
paper_title: A certifying algorithm for 3-colorability of P5-free graphs

paper_content:

We provide a certifying algorithm for the problem of deciding whether a P5- free graph is 3-colorable by showing there are exactly six finite graphs that are P5-free and not 3-colorable and minimal with respect to this property.
---
paper_title: Certifying Algorithms

paper_content:

A certifying algorithm is an algorithm that produces, with each output, a certificate or witness (easy-to-verify proof) that the particular output has not been compromised by a bug. A user of a certifying algorithm inputs x, receives the output y and the certificate w, and then checks, either manually or by use of a program, that w proves that y is a correct output for input x. In this way, he/she can be sure of the correctness of the output without having to trust the algorithm. We put forward the thesis that certifying algorithms are much superior to non-certifying algorithms, and that for complex algorithmic tasks, only certifying algorithms are satisfactory. Acceptance of this thesis would lead to a change of how algorithms are taught and how algorithms are researched. The widespread use of certifying algorithms would greatly enhance the reliability of algorithmic software. We survey the state of the art in certifying algorithms and add to it. In particular, we start a theory of certifying algorithms and prove that the concept is universal.
---
paper_title: Constructions of k-critical P5-free graphs

paper_content:

With respect to a hereditary class C of graphs, a k -chromatic graph G ? C is said to be k -critical if every proper subgraph of G belonging to C is k - 1 colorable. It is known that there is a finite number of 4-critical P 5 -free graphs. We construct an infinite set of k -critical P 5 -free graphs for every k ? 5 . We also prove that there are exactly eight 5-critical { P 5 , C 5 } -free graphs and thirteen 5-vertex-critical { P 5 , C 5 } -free graphs.
---
paper_title: On the parameterized complexity of coloring graphs in the absence of a linear forest

paper_content:

The k-Coloring problem is to decide whether a graph can be colored with at most k colors such that no two adjacent vertices receive the same color. The Listk-Coloring problem requires in addition that every vertex u must receive a color from some given set L(u)@?{1,...,k}. Let P"n denote the path on n vertices, and G+H and rH the disjoint union of two graphs G and H and r copies of H, respectively. We show that Listk-Coloring is fixed-parameter tractable on graphs with no induced rP"1+P"2 when parameterized by k+r, and that for any fixed integer r, the problem k-Coloring restricted to such graphs allows a polynomial kernel when parameterized by k. Finally, we show that Listk-Coloring is fixed-parameter tractable on graphs with no induced P"1+P"3 when parameterized by k.
---
paper_title: Closing Complexity Gaps for Coloring Problems on H-Free Graphs

paper_content:

If a graph G contains no subgraph isomorphic to some graph H, then G is called H-free. A coloring of a graph G = (V,E) is a mapping c: V → {1,2,…} such that no two adjacent vertices have the same color, i.e., c(u) ≠ c(v) if uv ∈ E; if |c(V)| ≤ k then c is a k-coloring. The Coloring problem is to test whether a graph has a coloring with at most k colors for some integer k. The Precoloring Extension problem is to decide whether a partial k-coloring of a graph can be extended to a k-coloring of the whole graph for some integer k. The List Coloring problem is to decide whether a graph allows a coloring, such that every vertex u receives a color from some given set L(u). By imposing an upper bound l on the size of each L(u) we obtain the l-List Coloring problem. We first classify the Precoloring Extension problem and the l-List Coloring problem for H-free graphs. We then show that 3-List Coloring is NP-complete for n-vertex graphs of minimum degree n − 2, i.e., for complete graphs minus a matching, whereas List Coloring is fixed-parameter tractable for this graph class when parameterized by the number of vertices of degree n − 2. Finally, for a fixed integer k > 0, the List k -Coloring problem is to decide whether a graph allows a coloring, such that every vertex u receives a color from some given set L(u) that must be a subset of {1,…,k}. We show that List 4-Coloring is NP-complete for P 6-free graphs, where P 6 is the path on six vertices. This completes the classification of List k -Coloring for P 6-free graphs.
---
paper_title: Complexity of coloring graphs without paths and cycles

paper_content:

Abstract Let P t and C l denote a path on t vertices and a cycle on l vertices, respectively. In this paper we study the k -coloring problem for ( P t , C l ) -free graphs. Bruce et al. (2009), and Maffray and Morel (2012) have proved that 3-colorability of P 5 -free graphs has a finite forbidden induced subgraphs characterization, while Hoang et al. (2015) have shown that k -colorability of P 5 -free graphs for k ≥ 4 does not. These authors have also shown, aided by a computer search, that 4-colorability of ( P 5 , C 5 ) -free graphs does have a finite forbidden induced subgraph characterization. We prove that for any k ≥ 1 , the k -colorability of ( P 6 , C 4 ) -free graphs has a finite forbidden induced subgraph characterization. For k = 3 and k = 4 , we provide the full lists of minimal forbidden induced subgraphs. As an application, we obtain certifying polynomial time algorithms for 3-coloring and 4-coloring ( P 6 , C 4 ) -free graphs. (Polynomial time algorithms have been previously obtained by Golovach, Paulusma, and Song, but those algorithms are not certifying.) To complement these results we show that in most other cases the k -coloring problem for ( P t , C l ) -free graphs is NP-complete. Specifically, we prove that the k -coloring problem is NP-complete for ( P t , C l ) -free graphs when – l = 5 , k ≥ 4 , and t ≥ 7 . – l ≥ 6 , k ≥ 5 , and t ≥ 6 . – l ≥ 6 but l ≠ 7 , k = 4 , and t ≥ 7 . – l ≥ 6 but l ≠ 9 , k = 4 , and t ≥ 9 . Our results almost completely classify the complexity for the cases when k ≥ 4 , l ≥ 4 , and identify the last few open cases.
---
paper_title: Some results on (a:b)-choosability

paper_content:

A solution to a problem of Erd\H{o}s, Rubin and Taylor is obtained by showing that if a graph $G$ is $(a:b)$-choosable, and $c/d > a/b$, then $G$ is not necessarily $(c:d)$-choosable. Applying probabilistic methods, an upper bound for the $k^{th}$ choice number of a graph is given. We also prove that a directed graph with maximum outdegree $d$ and no odd directed cycle is $(k(d+1):k)$-choosable for every $k \geq 1$. Other results presented in this article are related to the strong choice number of graphs (a generalization of the strong chromatic number). We conclude with complexity analysis of some decision problems related to graph choosability.
---
paper_title: Choosability of P5-Free Graphs

paper_content:

A graph is k-choosable if it admits a proper coloring of its vertices for every assignment of k (possibly different) allowed colors to choose from for each vertex. It is NP-hard to decide whether a given graph is k-choosable for k ? 3, and this problem is considered strictly harder than the k-coloring problem. Only few positive results are known on input graphs with a given structure. Here, we prove that the problem is fixed parameter tractable on P 5-free graphs when parameterized by k. This graph class contains the well known and widely studied class of cographs. Our result is surprising since the parameterized complexity of k-coloring is still open on P 5-free graphs. To give a complete picture, we show that the problem remains NP-hard on P 5-free graphs when k is a part of the input.
---
paper_title: The complexity of planar graph choosability

paper_content:

A graph $G$ is {\em $k$-choosable} if for every assignment of a set $S(v)$ of $k$ colors to every vertex $v$ of $G$, there is a proper coloring of $G$ that assigns to each vertex $v$ a color from $S(v)$. We consider the complexity of deciding whether a given graph is $k$-choosable for some constant $k$. In particular, it is shown that deciding whether a given planar graph is 4-choosable is NP-hard, and so is the problem of deciding whether a given planar triangle-free graph is 3-choosable. We also obtain simple constructions of a planar graph which is not 4-choosable and a planar triangle-free graph which is not 3-choosable.
---
paper_title: Choosability on H-free graphs

paper_content:

A graph is H-free if it has no induced subgraph isomorphic to H. We determine the computational complexity of the Choosability problem restricted to H-free graphs for every graph H that does not belong to {K"1","3,P"1+P"2,P"1+P"3,P"4}. We also show that if H is a linear forest, then the problem is fixed-parameter tractable when parameterized by k.
---
paper_title: Polynomial Algorithms for Perfect Graphs

paper_content:

We show that the weighted versions of the stable set problem, the clique problem, the coloring problem and the clique covering problem are solvable in polynomial time for perfect graphs. Our algorithms are based on the ellipsoid method and a polynomial time separation algorithm for a certain class of positive semidefinite matrices related to Lovasz's bound θ( G ) on the Shannon capacity of a graph. We show that θ G ) can be computed in polynomial time for all graphs G and also give a new characterization of perfect graphs in terms of this number θ( G ). In addition we prove that the problem of verifying that a graph is imperfect is in NP. Moreover, we show that the computation of the stability number and the fractional stability number of a graph are unrelated with respect to hardness (if P ≠ NP ).
---
paper_title: Precoloring extension. II. Graph classes related to bipartite graphs

paper_content:

We continue the study of the following general problem on vertex col- orings of graphs. Suppose that some vertices of a graph G are assigned to some colors. Can this "precoloring" be extended to a proper coloring of G with at most k colors (for some given k)? Here we investigate the complexity status of precoloring extendibility on some graph classes which are related to bipartite graphs, giving a complete solution for graphs with "co-chromatic number" 2, i.e., admitting a parti- tion V = V 1 ( V 2 of the vertex set V such that each V i induces a complete subgraph or an independent set. On one hand, we show that our problem is closely related to the bipartite maximum matching problem that leads to a polynomial solution for split graphs and for the complements of bipartite graphs. On the other hand, the problem turns out to be NP-complete on bipartite graphs.
---
paper_title: The List Chromatic Index of a Bipartite Multigraph

paper_content:

Abstract For a bipartite multigraph, the list chromatic index is equal to the chromatic index (which is, of course, the same as the maximum degree). This generalizes Janssen′s result on complete bipartite graphs Km, n with m ≠ n; in the case of Kn, n, it answers a question of Dinitz. (The list chromatic index of a multigraph is the least number n for which the edges can be colored so that adjacent edges get different colors, the color of each edge being chosen from an arbitrarily prescribed list of n different colors associated with that edge.)
---
paper_title: Choosability of P5-Free Graphs

paper_content:

A graph is k-choosable if it admits a proper coloring of its vertices for every assignment of k (possibly different) allowed colors to choose from for each vertex. It is NP-hard to decide whether a given graph is k-choosable for k ? 3, and this problem is considered strictly harder than the k-coloring problem. Only few positive results are known on input graphs with a given structure. Here, we prove that the problem is fixed parameter tractable on P 5-free graphs when parameterized by k. This graph class contains the well known and widely studied class of cographs. Our result is surprising since the parameterized complexity of k-coloring is still open on P 5-free graphs. To give a complete picture, we show that the problem remains NP-hard on P 5-free graphs when k is a part of the input.
---
paper_title: Choosability on H-free graphs

paper_content:

A graph is H-free if it has no induced subgraph isomorphic to H. We determine the computational complexity of the Choosability problem restricted to H-free graphs for every graph H that does not belong to {K"1","3,P"1+P"2,P"1+P"3,P"4}. We also show that if H is a linear forest, then the problem is fixed-parameter tractable when parameterized by k.
---
paper_title: Closing Complexity Gaps for Coloring Problems on H-Free Graphs

paper_content:

If a graph G contains no subgraph isomorphic to some graph H, then G is called H-free. A coloring of a graph G = (V,E) is a mapping c: V → {1,2,…} such that no two adjacent vertices have the same color, i.e., c(u) ≠ c(v) if uv ∈ E; if |c(V)| ≤ k then c is a k-coloring. The Coloring problem is to test whether a graph has a coloring with at most k colors for some integer k. The Precoloring Extension problem is to decide whether a partial k-coloring of a graph can be extended to a k-coloring of the whole graph for some integer k. The List Coloring problem is to decide whether a graph allows a coloring, such that every vertex u receives a color from some given set L(u). By imposing an upper bound l on the size of each L(u) we obtain the l-List Coloring problem. We first classify the Precoloring Extension problem and the l-List Coloring problem for H-free graphs. We then show that 3-List Coloring is NP-complete for n-vertex graphs of minimum degree n − 2, i.e., for complete graphs minus a matching, whereas List Coloring is fixed-parameter tractable for this graph class when parameterized by the number of vertices of degree n − 2. Finally, for a fixed integer k > 0, the List k -Coloring problem is to decide whether a graph allows a coloring, such that every vertex u receives a color from some given set L(u) that must be a subset of {1,…,k}. We show that List 4-Coloring is NP-complete for P 6-free graphs, where P 6 is the path on six vertices. This completes the classification of List k -Coloring for P 6-free graphs.
---
paper_title: The List Chromatic Index of a Bipartite Multigraph

paper_content:

Abstract For a bipartite multigraph, the list chromatic index is equal to the chromatic index (which is, of course, the same as the maximum degree). This generalizes Janssen′s result on complete bipartite graphs Km, n with m ≠ n; in the case of Kn, n, it answers a question of Dinitz. (The list chromatic index of a multigraph is the least number n for which the edges can be colored so that adjacent edges get different colors, the color of each edge being chosen from an arbitrarily prescribed list of n different colors associated with that edge.)
---
paper_title: Some upper bounds on the total and list chromatic numbers of multigraphs

paper_content:

In this paper we discuss some estimates for upper bounds on a number of chromatic parameters of a multigraph. In particular, we show that the total chromatic number for an n-order multigraph exceeds the chromatic index by the smallest t such that t! > n.
---
paper_title: Choosability on H-free graphs

paper_content:

A graph is H-free if it has no induced subgraph isomorphic to H. We determine the computational complexity of the Choosability problem restricted to H-free graphs for every graph H that does not belong to {K"1","3,P"1+P"2,P"1+P"3,P"4}. We also show that if H is a linear forest, then the problem is fixed-parameter tractable when parameterized by k.
---
paper_title: List coloring in the absence of two subgraphs

paper_content:

A list assignment of a graph G = ( V , E ) is a function L that assigns a list L ( u ) of so-called admissible colors to each u � V . The List Coloring problem is that of testing whether a given graph G = ( V , E ) has a coloring c that respects a given list assignment L , i.e., whether G has a mapping c : V � { 1 , 2 , � } such that (i) c ( u ) � c ( v ) whenever u v � E and (ii) c ( u ) � L ( u ) for all u � V . If a graph G has no induced subgraph isomorphic to some graph of a pair { H 1 , H 2 } , then G is called ( H 1 , H 2 ) -free. We completely characterize the complexity of List Coloring for ( H 1 , H 2 ) -free graphs.
---
paper_title: Coloring vertices of claw-free graphs in three colors

paper_content:

We study the computational complexity of the vertex 3-colorability problem in the class of claw-free graphs. Both the problem and the class received much attention in the literature, separately of each other. However, very little is known about the 3-colorability problem restricted to the class of claw-free graphs beyond the fact the problem is NP-complete under this restriction. In this paper we first strengthen this negative fact by revealing various further restrictions under which the problem remains NP-complete. Then we derive a number of positive results that deal with polynomially solvable cases of the problem in the class of claw-free graphs.
---
paper_title: A characterization of b-perfect graphs

paper_content:

A b-coloring is a coloring of the vertices of a graph such that each color class contains a vertex that has a neighbor in all other color classes, and the b-chromatic number of a graph $G$ is the largest integer $k$ such that $G$ admits a b-coloring with $k$ colors. A graph is b-perfect if the b-chromatic number is equal to the chromatic number for every induced subgraph of $G$. We prove that a graph is b-perfect if and only if it does not contain as an induced subgraph a member of a certain list of twenty-two graphs. This entails the existence of a polynomial-time recognition algorithm and of a polynomial-time algorithm for coloring exactly the vertices of every b-perfect graph.
---
paper_title: Some new hereditary classes where graph coloring remains NP-hard

paper_content:

The graph coloring problem is NP-hard in the set of all graphs. In this note we combine two problem reductions to provide a collection of hereditary classes of graphs for which the graph coloring problem remains NP-hard when restricted to it.
---
paper_title: Coloring the hypergraph of maximal cliques of a graph with no long path

paper_content:

We consider the problem of coloring the vertices of a graph so that no maximal clique of size at least two is monocolored. We solve the following question: Given a fixed graph F, does there exist an integer f(F) such that the hypergraph of maximal cliques of any F-free graph can be f(F)-colored? We show that the answer is positive if and only if all components of F are paths. In that case we give an estimate of f(F), and the proof contains a polynomial time algorithm to find such a coloring.
---
paper_title: Generalized coloring for tree-like graphs

paper_content:

We discuss the Precoloring Extension (PrExt) and the List Coloring (LiCol) problems for trees, partial k-trees and cographs in the decision and the construction versions. Both problems for partial k-trees are solved in linear time, when the number of colors is a constant and by O(¦V¦k+2)-algorithmsin general. For trees, we improve this to linear time. In contrast to that, PrExt and LiCol differ in complexity for cographs. While the first has a linear algorithm, the second is shown NP-complete. We give polynomial algorithms for the corresponding enumeration problems #PrExt and #LiCol on partial k-trees and trees and for #PrExt on cographs.
---
paper_title: Clique-width of Graph Classes Defined by Two Forbidden Induced Subgraphs

paper_content:

If a graph has no induced subgraph isomorphic to any graph in a finite family $\{H_1,\ldots,H_p\}$, it is said to be $(H_1,\ldots,H_p)$-free. The class of $H$-free graphs has bounded clique-width if and only if $H$ is an induced subgraph of the 4-vertex path $P_4$. We study the (un)boundedness of the clique-width of graph classes defined by two forbidden induced subgraphs $H_1$ and $H_2$. Prior to our study it was not known whether the number of open cases was finite. We provide a positive answer to this question. To reduce the number of open cases we determine new graph classes of bounded clique-width and new graph classes of unbounded clique-width. For obtaining the latter results we first present a new, generic construction for graph classes of unbounded clique-width. Our results settle the boundedness or unboundedness of the clique-width of the class of $(H_1,H_2)$-free graphs (i) for all pairs $(H_1,H_2)$, both of which are connected, except two non-equivalent cases, and (ii) for all pairs $(H_1,H_2)$, at least one of which is not connected, except 11 non-equivalent cases. We also consider classes characterized by forbidding a finite family of graphs $\{H_1,\ldots,H_p\}$ as subgraphs, minors and topological minors, respectively, and completely determine which of these classes have bounded clique-width. Finally, we show algorithmic consequences of our results for the graph colour
---
paper_title: A bound on the chromatic number of graphs without certain induced subgraphs

paper_content:

Abstract For each n , we obtain a (polynomial) bound on the chromatic number in terms of the maximum size of a complete subgraph, for graphs not having n · K 2 as an induced subgraph.
---
paper_title: Edge dominating set and colorings on graphs with fixed clique-width

paper_content:

We consider both the vertex and the edge versions of three graph partitioning problems. These problems are dominating set, list-q-coloring with costs (fixed number of colors q) and chromatic number. They are all known to be NP-hard in general. We show that all these problems (except edge-coloring) can be solved in polynomial time on graphs with clique-width bounded by some constant k, if the k-expression of the input graph is also given. In particular, we present the first polynomial algorithms (on these classes) for chromatic number, edge-dominating set and list-q-coloring with costs (fixed number of colors q, both vertex and edge versions). For the two list-q-coloring problems with costs, we even have linear algorithms. Since these classes of graphs include classes like P4-sparse graphs, distance hereditary graphs and graphs with bounded treewidth, our algorithms also apply to these graphs.
---
paper_title: Vertex 3-colorability of claw-free graphs

paper_content:

The 3-COLORABILITY problem is NP-complete in the class of claw-free graphs. In this paper we study the computational complexity of the problem in subclasses of claw-free graphs deﬁned by forbidding ﬁnitely many additional subgraphs (line graphs and claw-free graphs of bounded vertex degree being examples of such classes). We prove a necessary condition for the polynomial-time solvability of the problem in such classes and propose a linear-time solution for an inﬁnitely increasing hierarchy of classes that meet the condition. To develop such a solution for the basis of this hierarchy, we generalize the notion of locally connected graphs that has been recently studied in the context of the 3-COLORABILITY problem. ::: ::: Key words: Vertex 3-colorability; Claw-free graphs; Polynomial-time algorithm
---
paper_title: The chromatic number of {P5, K4}-free graphs

paper_content:

Abstract Gyarfas conjectured that for any tree T every T -free graph G with maximum clique size ω ( G ) is f T ( ω ( G ) ) -colorable, for some function f T that depends only on T and ω ( G ) . Moreover, he proved the conjecture when T is the path P k on k vertices. In the case of P 5 , the best values or bounds known so far are f P 5 ( 2 ) = 3 and f P 5 ( q ) ≤ 3 q − 1 . We prove here that f P 5 ( 3 ) = 5 .
---
paper_title: On the NP-completeness of the k-colorability problem for triangle-free graphs

paper_content:

Abstract We show that the question “Is a graph 3-colorable?” remains NP-complete when restricted to the class of triangle-free graphs with maximum degree 4. Likewise the question “Is a triangle-free graph k -colorable?” is shown to be NP-complete for any fixed value of k ⩾ 4.
---
paper_title: Complexity of coloring graphs without paths and cycles

paper_content:

Abstract Let P t and C l denote a path on t vertices and a cycle on l vertices, respectively. In this paper we study the k -coloring problem for ( P t , C l ) -free graphs. Bruce et al. (2009), and Maffray and Morel (2012) have proved that 3-colorability of P 5 -free graphs has a finite forbidden induced subgraphs characterization, while Hoang et al. (2015) have shown that k -colorability of P 5 -free graphs for k ≥ 4 does not. These authors have also shown, aided by a computer search, that 4-colorability of ( P 5 , C 5 ) -free graphs does have a finite forbidden induced subgraph characterization. We prove that for any k ≥ 1 , the k -colorability of ( P 6 , C 4 ) -free graphs has a finite forbidden induced subgraph characterization. For k = 3 and k = 4 , we provide the full lists of minimal forbidden induced subgraphs. As an application, we obtain certifying polynomial time algorithms for 3-coloring and 4-coloring ( P 6 , C 4 ) -free graphs. (Polynomial time algorithms have been previously obtained by Golovach, Paulusma, and Song, but those algorithms are not certifying.) To complement these results we show that in most other cases the k -coloring problem for ( P t , C l ) -free graphs is NP-complete. Specifically, we prove that the k -coloring problem is NP-complete for ( P t , C l ) -free graphs when – l = 5 , k ≥ 4 , and t ≥ 7 . – l ≥ 6 , k ≥ 5 , and t ≥ 6 . – l ≥ 6 but l ≠ 7 , k = 4 , and t ≥ 7 . – l ≥ 6 but l ≠ 9 , k = 4 , and t ≥ 9 . Our results almost completely classify the complexity for the cases when k ≥ 4 , l ≥ 4 , and identify the last few open cases.
---
paper_title: Complexity of Coloring Graphs without Forbidden Induced Subgraphs

paper_content:

We give a complete characterization of parameter graphs H for which the problem of coloring H-free graphs is polynomial and for which it is NP-complete. We further initiate a study of this problem for two forbidden subgraphs.
---
paper_title: Triangle-free 2P3-free graphs are 4-colorable

paper_content:

Abstract A graph is 2 P 3 -free if it does not contain two vertex-disjoint paths on three vertices as an induced subgraph. We prove that every triangle-free 2 P 3 -free graph is 4-colorable. This answers an open question posed by Broersma et al.
---
paper_title: Three-colourability and forbidden subgraphs. II: polynomial algorithms

paper_content:

In this paper we study the chromatic number for graphs with forbidden induced subgraphs. We focus our interest on graph classes (defined in terms of forbidden induced subgraphs) for which the question of 3-colourability can be decided in polynomial time and, if so, a proper 3-colouring can be determined also in polynomial time. Note that the 3-colourability decision problem is a well-known NP-complete problem, even for special graph classes, e.g. triangle-free and K1,5-free (Discrete Math. 162 (1-3) (1996) 313). Therefore, it is unlikely that there exists a polynomial algorithm deciding whether there exists a 3-colouring of a given graph in general. We present three different approaches to reach our goal. The first approach is purely a structural analysis of the graph class in consideration; the second one is a structural analysis of only the non-perfect K4-free members of the considered graph class; finally the last approach is based on propositional logic and bounded dominating subgraphs.
---
paper_title: Bounding Clique-Width via Perfect Graphs

paper_content:

Given two graphs $H_1$ and $H_2$, a graph $G$ is $(H_1,H_2)$-free if it contains no subgraph isomorphic to $H_1$ or $H_2$. We continue a recent study into the clique-width of $(H_1,H_2)$-free graphs and present three new classes of $(H_1,H_2)$-free graphs of bounded clique-width and one of unbounded clique-width. The four new graph classes have in common that one of their two forbidden induced subgraphs is the diamond (the graph obtained from a clique on four vertices by deleting one edge). To prove boundedness of clique-width for the first three cases we develop a technique based on bounding clique covering number in combination with reduction to subclasses of perfect graphs. We extend our proof of unboundedness for the fourth case to show that Graph Isomorphism is Graph Isomorphism-complete on the same graph class. We also show the implications of our results for the computational complexity of the Colouring problem restricted to $(H_1,H_2)$-free graphs.
---
paper_title: Choosability of P5-Free Graphs

paper_content:

A graph is k-choosable if it admits a proper coloring of its vertices for every assignment of k (possibly different) allowed colors to choose from for each vertex. It is NP-hard to decide whether a given graph is k-choosable for k ? 3, and this problem is considered strictly harder than the k-coloring problem. Only few positive results are known on input graphs with a given structure. Here, we prove that the problem is fixed parameter tractable on P 5-free graphs when parameterized by k. This graph class contains the well known and widely studied class of cographs. Our result is surprising since the parameterized complexity of k-coloring is still open on P 5-free graphs. To give a complete picture, we show that the problem remains NP-hard on P 5-free graphs when k is a part of the input.
---
paper_title: Approximating rank-width and clique-width quickly

paper_content:

Rank-width was defined by Oum and Seymour [2006] to investigate clique-width. They constructed an algorithm that either outputs a rank-decomposition of width at most f(k) for some function f or confirms that rank-width is larger than k in time O(vVv9log vVv) for an input graph G e (V,E) and a fixed k. We develop three separate algorithms of this kind with faster running time. We construct an O(vVv4)-time algorithm with f(k) e 3k + 1 by constructing a subroutine for the previous algorithm; we avoid generic algorithms minimizing submodular functions used by Oum and Seymour. Another one is an O(vVv3)-time algorithm with f(k) e 24k, achieved by giving a reduction from graphs to binary matroids; then we use an approximation algorithm for matroid branch-width by Hliněný [2005]. Finally we construct an O(vVv3)-time algorithm with f(k) e 3k − 1 by combining the ideas of the two previously cited papers.
---
paper_title: Colouring vertices of triangle-free graphs without forests

paper_content:

The vertex colouring problem is known to be NP-complete in the class of triangle-free graphs. Moreover, it is NP-complete in any subclass of triangle-free graphs defined by a finite collection of forbidden induced subgraphs, each of which contains a cycle. In this paper, we study the vertex colouring problem in subclasses of triangle-free graphs obtained by forbidding graphs without cycles, i.e., forests, and prove polynomial-time solvability of the problem in many classes of this type. In particular, our paper, combined with some previously known results, provides a complete description of the complexity status of the problem in subclasses of triangle-free graphs obtained by forbidding a forest with at most 6 vertices.
---
paper_title: Colouring of Graphs with Ramsey-Type Forbidden Subgraphs

paper_content:

A colouring of a graph G = (V,E) is a mapping c: V → {1,2,…} such that c(u) ≠ c(v) if uv ∈ E; if |c(V)| ≤ k then c is a k-colouring. The Colouring problem is that of testing whether a given graph has a k-colouring for some given integer k. If a graph contains no induced subgraph isomorphic to any graph in some family \({\cal H}\), then it is called \({\cal H}\)-free. The complexity of Colouring for \({\cal H}\)-free graphs with \(|{\cal H}|=1\) has been completely classified. When \(|{\cal H}|=2\), the classification is still wide open, although many partial results are known. We continue this line of research and forbid induced subgraphs {H 1,H 2}, where we allow H 1 to have a single edge and H 2 to have a single non-edge. Instead of showing only polynomial-time solvability, we prove that Colouring on such graphs is fixed-parameter tractable when parameterized by |H 1| + |H 2|. As a byproduct, we obtain the same result both for the problem of determining a maximum independent set and for the problem of determining a maximum clique.
---
paper_title: Coloring graphs without short cycles and long induced paths

paper_content:

The girth of a graph G is the length of a shortest cycle in G. For any fixed girth g ≥ 4 we determine a lower bound l(g) such that every graph with girth at least g and with no induced path on l(g) vertices is 3-colorable. In contrast, we show the existence of an integer l such that testing for 4-colorability is NP-complete for graphs with girth 4 and with no induced path on l vertices.
---
paper_title: ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES

paper_content:

Graphs of clique–width at most k were introduced by Courcelle, Engelfriet and Rozenberg (1993) as graphs which can be defined by k-expressions based on graph operations which use k vertex labels. In this paper we study the clique–width of perfect graph classes. On one hand, we show that every distance–hereditary graph, has clique–width at most 3, and a 3–expression defining it can be obtained in linear time. On the other hand, we show that the classes of unit interval and permutation graphs are not of bounded clique–width. More precisely, we show that for every $n\in {\mathcal N}$ there is a unit interval graph In and a permutation graph Hn having n2 vertices, each of whose clique–width is at least n. These results allow us to see the border within the hierarchy of perfect graphs between classes whose clique–width is bounded and classes whose clique–width is unbounded. Finally we show that every n×n square grid, $n\in {\mathcal N}$, n ≥ 3, has clique–width exactly n+1.
---
paper_title: 3-Colorability and forbidden subgraphs. I: Characterizing pairs

paper_content:

In this paper we investigate chromatic aspects for graphs with forbidden induced subgraphs with emphasis on the question of 3-colorability. In the main part all possible pairs (A,B) of forbidden induced subgraphs, s.t. every A- and B-free graph is 3-colorable, are determined. Moreover, this is embedded in a more general problem and the main result extends Vizing's classical edge coloring result.
---
paper_title: Exploring the complexity boundary between coloring and list-coloring

paper_content:

Many classes of graphs where the vertex coloring problem is polynomially solvable are known, the most prominent being the class of perfect graphs. However, the list-coloring problem is NP-complete for many subclasses of perfect graphs. In this work we explore the complexity boundary between vertex coloring and list-coloring on such subclasses of perfect graphs where the former admits polynomial-time algorithms but the latter is NP-complete. Our goal is to analyze the computational complexity of coloring problems lying “between” (from a computational complexity viewpoint) these two problems: precoloring extension, μ-coloring, and (γ,μ)-coloring.
---
paper_title: Closing Complexity Gaps for Coloring Problems on H-Free Graphs

paper_content:

If a graph G contains no subgraph isomorphic to some graph H, then G is called H-free. A coloring of a graph G = (V,E) is a mapping c: V → {1,2,…} such that no two adjacent vertices have the same color, i.e., c(u) ≠ c(v) if uv ∈ E; if |c(V)| ≤ k then c is a k-coloring. The Coloring problem is to test whether a graph has a coloring with at most k colors for some integer k. The Precoloring Extension problem is to decide whether a partial k-coloring of a graph can be extended to a k-coloring of the whole graph for some integer k. The List Coloring problem is to decide whether a graph allows a coloring, such that every vertex u receives a color from some given set L(u). By imposing an upper bound l on the size of each L(u) we obtain the l-List Coloring problem. We first classify the Precoloring Extension problem and the l-List Coloring problem for H-free graphs. We then show that 3-List Coloring is NP-complete for n-vertex graphs of minimum degree n − 2, i.e., for complete graphs minus a matching, whereas List Coloring is fixed-parameter tractable for this graph class when parameterized by the number of vertices of degree n − 2. Finally, for a fixed integer k > 0, the List k -Coloring problem is to decide whether a graph allows a coloring, such that every vertex u receives a color from some given set L(u) that must be a subset of {1,…,k}. We show that List 4-Coloring is NP-complete for P 6-free graphs, where P 6 is the path on six vertices. This completes the classification of List k -Coloring for P 6-free graphs.
---
paper_title: Upper bounds to the clique width of graphs

paper_content:

Abstract Hierarchical decompositions of graphs are interesting for algorithmic purposes. Many NP complete problems have linear complexity on graphs with tree-decompositions of bounded width. We investigate alternate hierarchical decompositions that apply to wider classes of graphs and still enjoy good algorithmic properties. These decompositions are motivated and inspired by the study of vertex-replacement context-free graph grammars. The complexity measure of graphs associated with these decompositions is called clique width. In this paper we bound the clique width of a graph in terms of its tree width on the one hand, and of the clique width of its edge complement on the other.
---
paper_title: Precoloring extension. III. Classes of perfect graphs

paper_content:

We continue the study of the following general problem on the vertex colourings of graphs. Suppose that some vertices of a graph G are assigned to some colours. Can this ‘precolouring’ be extended to a proper colouring of G with at most k colours (for some given k )? Here we investigate the complexity status of precolouring extendibility on some classes of perfect graphs, giving good characterizations (necessary and sufficient conditions) that lead to algorithms with linear or polynomial running time. It is also shown how a larger subclass of perfect graphs can be derived from graphs containing no induced path on four vertices.
---
paper_title: Complexity of coloring graphs without paths and cycles

paper_content:

Abstract Let P t and C l denote a path on t vertices and a cycle on l vertices, respectively. In this paper we study the k -coloring problem for ( P t , C l ) -free graphs. Bruce et al. (2009), and Maffray and Morel (2012) have proved that 3-colorability of P 5 -free graphs has a finite forbidden induced subgraphs characterization, while Hoang et al. (2015) have shown that k -colorability of P 5 -free graphs for k ≥ 4 does not. These authors have also shown, aided by a computer search, that 4-colorability of ( P 5 , C 5 ) -free graphs does have a finite forbidden induced subgraph characterization. We prove that for any k ≥ 1 , the k -colorability of ( P 6 , C 4 ) -free graphs has a finite forbidden induced subgraph characterization. For k = 3 and k = 4 , we provide the full lists of minimal forbidden induced subgraphs. As an application, we obtain certifying polynomial time algorithms for 3-coloring and 4-coloring ( P 6 , C 4 ) -free graphs. (Polynomial time algorithms have been previously obtained by Golovach, Paulusma, and Song, but those algorithms are not certifying.) To complement these results we show that in most other cases the k -coloring problem for ( P t , C l ) -free graphs is NP-complete. Specifically, we prove that the k -coloring problem is NP-complete for ( P t , C l ) -free graphs when – l = 5 , k ≥ 4 , and t ≥ 7 . – l ≥ 6 , k ≥ 5 , and t ≥ 6 . – l ≥ 6 but l ≠ 7 , k = 4 , and t ≥ 7 . – l ≥ 6 but l ≠ 9 , k = 4 , and t ≥ 9 . Our results almost completely classify the complexity for the cases when k ≥ 4 , l ≥ 4 , and identify the last few open cases.
---
paper_title: Constructions of k-critical P5-free graphs

paper_content:

With respect to a hereditary class C of graphs, a k -chromatic graph G ? C is said to be k -critical if every proper subgraph of G belonging to C is k - 1 colorable. It is known that there is a finite number of 4-critical P 5 -free graphs. We construct an infinite set of k -critical P 5 -free graphs for every k ? 5 . We also prove that there are exactly eight 5-critical { P 5 , C 5 } -free graphs and thirteen 5-vertex-critical { P 5 , C 5 } -free graphs.
---
paper_title: List-Coloring Claw-Free Graphs with Small Clique Number

paper_content:

Chudnovsky and Seymour proved that every connected claw-free graph that contains a stable set of size 3 has chromatic number at most twice its clique number. We improve this for small clique size, showing that every claw-free graph with clique number at most 3 is 4-choosable and every claw-free graph with clique number at most 4 is 7-choosable. These bounds are tight.
---
paper_title: List coloring in the absence of two subgraphs

paper_content:

A list assignment of a graph G = ( V , E ) is a function L that assigns a list L ( u ) of so-called admissible colors to each u � V . The List Coloring problem is that of testing whether a given graph G = ( V , E ) has a coloring c that respects a given list assignment L , i.e., whether G has a mapping c : V � { 1 , 2 , � } such that (i) c ( u ) � c ( v ) whenever u v � E and (ii) c ( u ) � L ( u ) for all u � V . If a graph G has no induced subgraph isomorphic to some graph of a pair { H 1 , H 2 } , then G is called ( H 1 , H 2 ) -free. We completely characterize the complexity of List Coloring for ( H 1 , H 2 ) -free graphs.
---
paper_title: Finding topological subgraphs is fixed-parameter tractable

paper_content:

We show that for every fixed undirected graph $H$, there is a $O(|V(G)|^3)$ time algorithm that tests, given a graph $G$, if $G$ contains $H$ as a topological subgraph (that is, a subdivision of $H$ is subgraph of $G$). This shows that topological subgraph testing is fixed-parameter tractable, resolving a longstanding open question of Downey and Fellows from 1992. As a corollary, for every $H$ we obtain an $O(|V(G)|^3)$ time algorithm that tests if there is an immersion of $H$ into a given graph $G$. This answers another open question raised by Downey and Fellows in 1992.
---
paper_title: Graph Minors .XIII. The Disjoint Paths Problem

paper_content:

Abstract We describe an algorithm, which for fixed k ≥ 0 has running time O (| V(G) | 3 ), to solve the following problem: given a graph G and k pairs of vertices of G , decide if there are k mutually vertex-disjoint paths of G joining the pairs.
---
paper_title: Generalized coloring for tree-like graphs

paper_content:

We discuss the Precoloring Extension (PrExt) and the List Coloring (LiCol) problems for trees, partial k-trees and cographs in the decision and the construction versions. Both problems for partial k-trees are solved in linear time, when the number of colors is a constant and by O(¦V¦k+2)-algorithmsin general. For trees, we improve this to linear time. In contrast to that, PrExt and LiCol differ in complexity for cographs. While the first has a linear algorithm, the second is shown NP-complete. We give polynomial algorithms for the corresponding enumeration problems #PrExt and #LiCol on partial k-trees and trees and for #PrExt on cographs.
---
paper_title: Graph minors. V. Excluding a planar graph

paper_content:

We prove that for every planar graph H there is a number w such that every graph with no minor isomorphic to H can be constructed from graphs with at most w vertices, by piecing them together in a tree structure. This has several consequences; for example, it implies that: (i) if A is a set of graphs such that no member is isomorphic to a minor of another, and some member of A is planar, then A is finite; (ii) for every fixed planar graph H there is a polynomial time algorithm to test if an arbitrary graph has a minor isomorphic to H; (iii) there is a generalization of a theorem of Erdos and Posa (concerning the maximum number of disjoint circuits in a graph) to planar structures other than circuits.
---
paper_title: Coloring Graphs Characterized by a Forbidden Subgraph

paper_content:

The Coloring problem is to test whether a given graph can be colored with at most k colors for some given k, such that no two adjacent vertices receive the same color. The complexity of this problem on graphs that do not contain some graph H as an induced subgraph is known for each fixed graph H. A natural variant is to forbid a graph H only as a subgraph. We call such graphs strongly H-free and initiate a complexity classification of Coloring for strongly H-free graphs. We show that Coloring is NP-complete for strongly H-free graphs, even for k=3, when H contains a cycle, has maximum degree at least five, or contains a connected component with two vertices of degree four. We also give three conditions on a forest H of maximum degree at most four and with at most one vertex of degree four in each of its connected components, such that Coloring is NP-complete for strongly H-free graphs even for k=3. Finally, we classify the computational complexity of Coloring on strongly H-free graphs for all fixed graphs H up to seven vertices. In particular, we show that Coloring is polynomial-time solvable when H is a forest that has at most seven vertices and maximum degree at most four.
---
paper_title: Some simplified NP-complete graph problems

paper_content:

Abstract It is widely believed that showing a problem to be NP -complete is tantamount to proving its computational intractability. In this paper we show that a number of NP -complete problems remain NP -complete even when their domains are substantially restricted. First we show the completeness of Simple Max Cut (Max Cut with edge weights restricted to value 1), and, as a corollary, the completeness of the Optimal Linear Arrangement problem. We then show that even if the domains of the Node Cover and Directed Hamiltonian Path problems are restricted to planar graphs, the two problems remain NP -complete, and that these and other graph problems remain NP -complete even when their domains are restricted to graphs with low node degrees. For Graph 3-Colorability, Node Cover, and Undirected Hamiltonian Circuit, we determine essentially the lowest possible upper bounds on node degree for which the problems remain NP -complete.
---
paper_title: On the complexity of some colorful problems parameterized by treewidth

paper_content:

In this paper, we study the complexity of several coloring problems on graphs, parameterized by the treewidth of the graph.1.The List Coloring problem takes as input a graph G, together with an assignment to each vertex v of a set of colors C"v. The problem is to determine whether it is possible to choose a color for vertex v from the set of permitted colors C"v, for each vertex, so that the obtained coloring of G is proper. We show that this problem is W[1]-hard, parameterized by the treewidth of G. The closely related Precoloring Extension problem is also shown to be W[1]-hard, parameterized by treewidth. 2.An equitable coloring of a graph G is a proper coloring of the vertices where the numbers of vertices having any two distinct colors differs by at most one. We show that the problem is hard for W[1], parameterized by the treewidth plus the number of colors. We also show that a list-based variation, List Equitable Coloring is W[1]-hard for forests, parameterized by the number of colors on the lists. 3.The list chromatic number@g"l(G) of a graph G is defined to be the smallest positive integer r, such that for every assignment to the vertices v of G, of a list L"v of colors, where each list has length at least r, there is a choice of one color from each vertex list L"v yielding a proper coloring of G. We show that the problem of determining whether @g"l(G)=
---

Title: A Survey on the Computational Complexity of Colouring Graphs with Forbidden Subgraphs

Section 1: Introduction
Description 1: Introduce the topic of graph colouring, its importance, and provide an overview of the paper's goals and structure.

Section 2: Graph Colouring Problems
Description 2: Define basic graph colouring terminologies and introduce the various graph colouring problems studied in the survey.

Section 3: Precolouring Extension Problems
Description 3: Explain precolouring extension problems and discuss the computational complexity associated with them.

Section 4: List Colouring Problems
Description 4: Discuss list colouring problems and their complexity classifications, including their variations and subtleties.

Section 5: Choosability Problems
Description 5: Define choosability problems and describe their implications in graph colouring, including computational complexity results.

Section 6: Notation and Terminology
Description 6: Provide definitions of graph classes, notation, and other terminology used throughout the survey to ensure clarity.

Section 7: Results and Open Problems for H-Free Graphs
Description 7: Present the main results and open problems related to H-free graphs, including the complexity of various colouring problems.

Section 8: Parameterized Complexity Theory
Description 8: Introduce parameterized complexity theory and its application to graph colouring problems, highlighting known results and open questions.

Section 9: Certifying Algorithms
Description 9: Discuss certifying algorithms for graph colouring problems and their significance, including existing algorithms and open problems.

Section 10: Results and Open Problems for (H1, H2)-Free Graphs
Description 10: Summarize the findings and unresolved questions for graph classes characterized by two forbidden subgraphs.

Section 11: Graph Classes Defined by Other Forbidden Patterns
Description 11: Explore the complexity of colouring problems for other graph classes, such as strongly H-free graphs, H-minor-free graphs, and H-topological-minor-free graphs, including known results and open problems.