A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs

DOI10.1002/jgt.22028zbMath1359.05039arXiv1407.1482OpenAlexW2962956065MaRDI QIDQ2978179

Jian Song, Matthew Johnson, Petr A. Golovach, Daniël Paulusma

Publication date: 21 April 2017

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1407.1482

zbMATH Keywords

graph coloring choosability list coloring precoloring extension forbidden induced subgraph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Algorithms for the rainbow vertex coloring problem on graph classes, Forbidden induced subgraphs for perfectness of claw-free graphs of independence number at least 4, The vertex colourability problem for $\{\text{claw}, \text{butterfly}\}$-free graphs is polynomial-time solvable, A branch and price algorithm for list coloring problem, An intractability result for the vertex 3-colourability problem, Forbidden induced pairs for perfectness and $\omega$-colourability of graphs, Partitioning $H$-free graphs of bounded diameter, Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem, Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter, Boundary classes for graph problems involving non-local properties, Colouring diamond-free graphs, Regular pattern-free coloring, The weighted coloring problem for two graph classes characterized by small forbidden induced structures, Steiner trees for hereditary graph classes: a treewidth perspective, The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs, Efficient solvability of the weighted vertex coloring problem for some hereditary class of graphs with $5$-vertex prohibitions, Complete complexity dichotomy for $7$-edge forbidden subgraphs in the edge coloring problem, Colouring square-free graphs without long induced paths., Reducing the chromatic number by vertex or edge deletions, Colouring $(P_r + P_s)$-free graphs, On the chromatic number of ($P_6$, diamond)-free graphs, Certifying coloring algorithms for graphs without long induced paths, Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs, Complexity Dichotomy for List-5-Coloring with a Forbidden Induced Subgraph, Efficient solvability of the weighted vertex coloring problem for some two hereditary graph classes, A refinement on the structure of vertex-critical $(P_5, \mathrm{gem})$-free graphs, Complexity of $C_k$-coloring in hereditary classes of graphs, Finding matching cuts in $H$-free graphs, Clique‐width: Harnessing the power of atoms, 3-coloring $C_4$ or $C_3$-free diameter two graphs, The $r$-coloring and maximum stable set problem in hypergraphs with bounded matching number and edge size, Unnamed Item, Clique-Width for Graph Classes Closed under Complementation, 3-colouring $P_t$-free graphs without short odd cycles, On algorithmic applications of sim-width and mim-width of $(H_1,H_2)$-free graphs, On colouring $(2P_2,H)$-free and $(P_5,H)$-free graphs, A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs, Better 3-coloring algorithms: excluding a triangle and a seven vertex path, List 3-coloring graphs with no induced $P_6 + rP_3$, Critical vertices and edges in $H$-free graphs, On Computational Aspects of Greedy Partitioning of Graphs, Polynomial $\chi $-binding functions and forbidden induced subgraphs: a survey, Polynomial cases for the vertex coloring problem, List $k$-colouring $P_t$-free graphs: a mim-width perspective, Independent feedback vertex set for $P_5$-free graphs, Classifying $k$-edge colouring for $H$-free graphs, 3-Colorable Subclasses of $P_8$-Free Graphs, Contracting to a longest path in H-free graphs, The computational complexity of weighted vertex coloring for $\{P_5,K_{2,3},K^+_{2,3}\}$-free graphs, Unnamed Item, Combining lithography and directed self assembly for the manufacturing of vias: connections to graph coloring problems, integer programming formulations, and numerical experiments, Approximately coloring graphs without long induced paths, Three-coloring and list three-coloring of graphs without induced paths on seven vertices, Connected vertex cover for $(sP_1+P_5)$-free graphs, Clique-width and well-quasi-ordering of triangle-free graph classes, Obstructions for three-coloring graphs without induced paths on six vertices, On cycle transversals and their connected variants in the absence of a small linear forest, Unnamed Item, Colouring graphs of bounded diameter in the absence of small cycles, On 3-coloring of $(2P_4,C_5)$-free graphs, Colouring graphs of bounded diameter in the absence of small cycles, Obstructions for Three-Coloring and List Three-Coloring $H$-Free Graphs, On 3-coloring of $(2P_4,C_5)$-free graphs, The intersection of two vertex coloring problems, On list $k$-coloring convex bipartite graphs, Hard problems that quickly become very easy, Algorithms for the Rainbow Vertex Coloring Problem on Graph Classes, Colouring (P_r+P_s)-Free Graphs, Colouring H-free graphs of bounded diameter., Open Problems on Graph Coloring for Special Graph Classes, $(2P_2,K_4)$-Free Graphs are 4-Colorable, Colouring square-free graphs without long induced paths, Connected greedy coloring of $H$-free graphs, DP-degree colorable hypergraphs, Parameterized Pre-Coloring Extension and List Coloring Problems, Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure, Faster 3-Coloring of Small-Diameter Graphs, Injective colouring for H-free graphs

Uses Software

CriticalPfreeGraphs

Cites Work