Colouring (P_r+P_s)-Free Graphs
From MaRDI portal
Publication:5090995
DOI10.4230/LIPIcs.ISAAC.2018.5OpenAlexW2962816679MaRDI QIDQ5090995
Josef Malík, Daniël Paulusma, Jana Novotná, Veronika Slívová, Tereza Klimošová, Tomáš Masařík
Publication date: 21 July 2022
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/9953/pdf/LIPIcs-ISAAC-2018-5.pdf
Related Items (7)
Colouring \((P_r + P_s)\)-free graphs ⋮ Unnamed Item ⋮ Better 3-coloring algorithms: excluding a triangle and a seven vertex path ⋮ Classifying \(k\)-edge colouring for \(H\)-free graphs ⋮ Colouring graphs of bounded diameter in the absence of small cycles ⋮ Colouring (P_r+P_s)-Free Graphs ⋮ Colouring H-free graphs of bounded diameter.
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
- Updating the complexity status of coloring graphs without a fixed induced linear forest
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- The complexity of colouring problems on dense graphs
- 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
- Three-colourability and forbidden subgraphs. II: Polynomial algorithms
- Triangle-free graphs with no six-vertex induced path
- On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs
- Three-coloring and list three-coloring of graphs without induced paths on seven vertices
- Vertex colouring and forbidden subgraphs -- a survey
- Three complexity results on coloring \(P_k\)-free graphs
- Closing complexity gaps for coloring problems on \(H\)-free graphs
- List coloring in the absence of a linear forest
- \(H\)-colouring \(P_t\)-free graphs in subexponential time
- On the complexity of 4-coloring graphs without long induced paths
- Open Problems on Graph Coloring for Special Graph Classes
- 4‐Coloring P 6 ‐Free Graphs with No Induced 5‐Cycles
- A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
- The NP-Completeness of Edge-Coloring
- Graph colorings with local constraints -- a survey
- Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
- 3-Colorable Subclasses of $P_8$-Free Graphs
- NP completeness of finding the chromatic index of regular graphs
- Colouring (P_r+P_s)-Free Graphs
- Independent Feedback Vertex Set for P_5-free Graphs
- Polynomial-time algorithm for Maximum Weight Independent Set on P6-free graphs
- The complexity of satisfiability problems
This page was built for publication: Colouring (P_r+P_s)-Free Graphs
