Complexity of the list homomorphism problem in hereditary graph classes
From MaRDI portal
Cites work
- H-coloring dichotomy revisited
- \(H\)-colouring \(P_t\)-free graphs in subexponential time
- A new line of attack on the dichotomy conjecture
- A survey on the computational complexity of coloring graphs with forbidden subgraphs
- Bi‐arc graphs and the complexity of list homomorphisms
- Certifying coloring algorithms for graphs without long induced paths
- Closing complexity gaps for coloring problems on \(H\)-free graphs
- Complexity of C_K-coloring in hereditary classes of graphs
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- Descriptive complexity of list H-coloring problems in logspace: a refined dichotomy
- Dichotomy for tree-structured trigraph list homomorphism problems
- Four-coloring \(P_6\)-free graphs
- scientific article; zbMATH DE number 7228418 (Why is no real title available?)
- scientific article; zbMATH DE number 7651174 (Why is no real title available?)
- scientific article; zbMATH DE number 7651213 (Why is no real title available?)
- Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
- List homomorphisms and circular arc graphs
- List homomorphisms of graphs with bounded degrees
- List homomorphisms to reflexive graphs
- List Partitions
- NP completeness of finding the chromatic index of regular graphs
- On the complexity of H-coloring
- Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs
- Quasi-polynomial-time algorithm for independent set in P_t-free graphs via shrinking the space of induced paths
- Space complexity of list H-colouring: a dichotomy
- Subexponential algorithms for variants of the homomorphism problem in string graphs
- The NP-Completeness of Edge-Coloring
- The three-in-a-tree problem
- Three-coloring and list three-coloring of graphs without induced paths on seven vertices
- Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
This page was built for publication: Complexity of the list homomorphism problem in hereditary graph classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7231578)
