scientific article; zbMATH DE number 7651174
From MaRDI portal
Publication:5874504
DOI10.4230/LIPICS.ESA.2020.35MaRDI QIDQ5874504FDOQ5874504
Authors: Maria Chudnovsky, Jason King, Michał Pilipczuk, Paweł Rząėwski, Sophie Spirkl 
Publication date: 7 February 2023
Title of this publication is not available (Why is that?)
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
- Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
- Linear time solvable optimization problems on graphs of bounded clique-width
- Independent set in \(P_5\)-free graphs in polynomial time
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- On maximal independent sets of vertices in claw-free graphs
- Large Induced Subgraphs via Triangulations and CMSO
- A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
- Polynomial algorithm for finding the largest independent sets in graphs without forks
- The Erdős-Hajnal conjecture for bull-free graphs
- A dichotomy for minimum cost graph homomorphisms
- Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
- Polynomial-time algorithm for maximum weight independent set on \(P_6\)-free graphs
- Odd holes in bull-free graphs
- \(H\)-colouring \(P_t\)-free graphs in subexponential time
- Four-coloring \(P_6\)-free graphs
- Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs
- Three-coloring and list three-coloring of graphs without induced paths on seven vertices
- A subexponential-time algorithm for the maximum independent set problem in \(P_t\)-free graphs
- Closing complexity gaps for coloring problems on \(H\)-free graphs
- Title not available (Why is that?)
- Subexponential algorithms for variants of the homomorphism problem in string graphs
- Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs
Cited In (7)
- Bounding the Mim-Width of Hereditary Graph Classes.
- Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes
- Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes
- Title not available (Why is that?)
- List \(k\)-colouring \(P_t\)-free graphs: a mim-width perspective
- Some new hereditary classes where graph coloring remains NP-hard
- Bounding the mim‐width of 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)
