Colouring (P_r+P_s)-Free Graphs
From MaRDI portal
Recommendations
Cites work
- 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
- 3-colorable subclasses of \(P_8\)-free graphs
- 4‐Coloring P 6 ‐Free Graphs with No Induced 5‐Cycles
- \(H\)-colouring \(P_t\)-free graphs in subexponential time
- A survey on the computational complexity of coloring graphs with forbidden subgraphs
- Closing complexity gaps for coloring problems on \(H\)-free graphs
- Coloring graphs with forbidden induced subgraphs
- Colouring (P_r+P_s)-Free Graphs
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- Graph colorings with local constraints -- a survey
- scientific article; zbMATH DE number 3503283 (Why is no real title available?)
- scientific article; zbMATH DE number 1341914 (Why is no real title available?)
- scientific article; zbMATH DE number 2044943 (Why is no real title available?)
- scientific article; zbMATH DE number 821271 (Why is no real title available?)
- Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
- Independent Feedback Vertex Set for P₅-free Graphs
- List coloring in the absence of a linear forest
- NP completeness of finding the chromatic index of regular graphs
- On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs
- On the complexity of 4-coloring graphs without long induced paths
- Open problems on graph coloring for special graph classes
- Polynomial-time algorithm for maximum weight independent set on \(P_6\)-free graphs
- The complexity of coloring graphs without long induced paths
- The complexity of colouring problems on dense graphs
- The complexity of satisfiability problems
- The NP-Completeness of Edge-Coloring
- Three complexity results on coloring \(P_k\)-free graphs
- Three-coloring and list three-coloring of graphs without induced paths on seven vertices
- Three-colourability and forbidden subgraphs. II: Polynomial algorithms
- Triangle-free graphs with no six-vertex induced path
- Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
- Updating the complexity status of coloring graphs without a fixed induced linear forest
- Vertex colouring and forbidden subgraphs -- a survey
Cited in
(13)- Colouring of (P₃ P₂)-free graphs
- Classifying \(k\)-edge colouring for \(H\)-free graphs
- 4-coloring \(H\)-free graphs when \(H\) is small
- Colouring \((P_r + P_s)\)-free graphs
- Better 3-coloring algorithms: excluding a triangle and a seven vertex path
- Coloring (gem, co‐gem)‐free graphs
- Colouring (P_r+P_s)-Free Graphs
- Colouring H-free graphs of bounded diameter.
- scientific article; zbMATH DE number 7651161 (Why is no real title available?)
- On 3-coloring of \((2P_4,C_5)\)-free graphs
- Colouring graphs of bounded diameter in the absence of small cycles
- Making an H H‐free graph k k‐colorable
- Acyclic, star and injective colouring: a complexity picture for H-free graphs
This page was built for publication: Colouring (P_r+P_s)-Free Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090995)
