scientific article; zbMATH DE number 7651174
From MaRDI portal
Publication:5874504
Recommendations
- Finding Large H-Colorable Subgraphs in Hereditary Graph Classes
- Hereditary graph classes: When the complexities of <scp>coloring</scp> and <scp>clique cover</scp> coincide
- Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes
- Complexity of C_K-coloring in hereditary classes of graphs
- Complexity of \(C_k\)-coloring in hereditary classes of graphs
- scientific article; zbMATH DE number 1286302
- scientific article; zbMATH DE number 1983292
- Locally bounded hereditary subclasses of k-colourable graphs
- Some new hereditary classes where graph coloring remains NP-hard
- scientific article; zbMATH DE number 1696630
Cites work
- \(H\)-colouring \(P_t\)-free graphs in subexponential time
- A dichotomy for minimum cost graph homomorphisms
- A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
- A subexponential-time algorithm for the maximum independent set problem in \(P_t\)-free graphs
- Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
- Closing complexity gaps for coloring problems on \(H\)-free graphs
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- Four-coloring \(P_6\)-free graphs
- scientific article; zbMATH DE number 7650231 (Why is no real title available?)
- Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
- Independent set in P₅-free graphs in polynomial time
- Large Induced Subgraphs via Triangulations and CMSO
- Linear time solvable optimization problems on graphs of bounded clique-width
- Odd holes in bull-free graphs
- On maximal independent sets of vertices in claw-free graphs
- Polynomial algorithm for finding the largest independent sets in graphs without forks
- Polynomial-time algorithm for maximum weight independent set on \(P_6\)-free graphs
- Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs
- Subexponential algorithms for variants of the homomorphism problem in string graphs
- Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs
- The Erdős-Hajnal conjecture for bull-free graphs
- Three-coloring and list three-coloring of graphs without induced paths on seven vertices
Cited in
(8)- Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes
- List k-colouring P_t-free graphs: a mim-width perspective
- scientific article; zbMATH DE number 1286302 (Why is no real title available?)
- Finding Large H-Colorable Subgraphs in Hereditary Graph Classes
- Some new hereditary classes where graph coloring remains NP-hard
- Bounding the mim‐width of hereditary graph classes
- Bounding the Mim-Width of Hereditary Graph Classes.
- Complexity of the list homomorphism problem in hereditary graph classes
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5874504)
