The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs (Q2352049): Difference between revisions

@@ Property / author @@
-Dmitriy S. Malyshev
@@ Property / author: Dmitriy S. Malyshev / rank @@
-Normal rank
@@ Property / author @@
+Dmitriy S. Malyshev
@@ Property / author: Dmitriy S. Malyshev / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/j.disc.2015.04.019
+Normal rank
@@ Property / OpenAlex ID @@
+W1012466235
@@ Property / OpenAlex ID: W1012466235 / rank @@
+Normal rank
@@ Property / cites work @@
+On easy and hard hereditary classes of graphs with respect to the independent set problem
+Normal rank
@@ Property / cites work @@
+NP-hard graph problems and boundary classes of graphs
+Normal rank
@@ Property / cites work @@
+Boundary classes of graphs for the dominating set problem
+Normal rank
@@ Property / cites work @@
+Updating the complexity status of coloring graphs without a fixed induced linear forest
+Normal rank
@@ Property / cites work @@
+Q5782525
@@ Property / cites work: Q5782525 / rank @@
+Normal rank
@@ Property / cites work @@
+The strong perfect graph theorem
@@ Property / cites work: The strong perfect graph theorem / rank @@
+Normal rank
@@ Property / cites work @@
+Colouring vertices of triangle-free graphs without forests
+Normal rank
@@ Property / cites work @@
+List coloring in the absence of two subgraphs
@@ Property / cites work: List coloring in the absence of two subgraphs / rank @@
+Normal rank
@@ Property / cites work @@
+-coloring \(H\)-free graphs when \(H\) is small
@@ Property / cites work: 4-coloring \(H\)-free graphs when \(H\) is small / rank @@
+Normal rank
@@ Property / cites work @@
+The ellipsoid method and its consequences in combinatorial optimization
+Normal rank
@@ Property / cites work @@
+The 3-Colorability Problem on Graphs with Maximum Degree Four
+Normal rank
@@ Property / cites work @@
+Boundary properties of graphs for algorithmic graph problems
+Normal rank
@@ Property / cites work @@
+Q4448764
@@ Property / cites work: Q4448764 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3558598
@@ Property / cites work: Q3558598 / rank @@
+Normal rank
@@ Property / cites work @@
+Vertex coloring of graphs with few obstructions
@@ Property / cites work: Vertex coloring of graphs with few obstructions / rank @@
+Normal rank
@@ Property / cites work @@
+On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
+Normal rank
@@ Property / cites work @@
+The coloring problem for classes with two small obstructions
+Normal rank
@@ Property / cites work @@
+Two cases of polynomial-time solvability for the coloring problem
+Normal rank
@@ Property / cites work @@
+Q3115195
@@ Property / cites work: Q3115195 / rank @@
+Normal rank
@@ Property / cites work @@
+On intersection and symmetric difference of families of boundary classes in the problems on colouring and on the chromatic number
+Normal rank
@@ Property / cites work @@
+Three-colourability and forbidden subgraphs. II: Polynomial algorithms
+Normal rank