Deciding k-colorability of P₅-free graphs in polynomial time
From MaRDI portal
(Redirected from Publication:848637)
Deciding \(k\)-colorability of \(P 5\)-free graphs in polynomial time
Deciding \(k\)-colorability of \(P 5\)-free graphs in polynomial time
Recommendations
Cites work
- scientific article; zbMATH DE number 3882470 (Why is no real title available?)
- scientific article; zbMATH DE number 4204394 (Why is no real title available?)
- scientific article; zbMATH DE number 2044943 (Why is no real title available?)
- scientific article; zbMATH DE number 2203240 (Why is no real title available?)
- 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- Coloration de graphes : fondements et applications
- Dominating cliques in \(P_ 5\)-free graphs
- Matrix multiplication via arithmetic progressions
- On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
- On the complexity of 4-coloring graphs without long induced paths
- On the hardness of approximating the chromatic number
- Optimizing weakly triangulated graphs
- Permutation Graphs and Transitive Graphs
- The NP-Completeness of Edge-Coloring
- The complexity of coloring graphs without long induced paths
- Three-colourability and forbidden subgraphs. II: Polynomial algorithms
- Vertex colouring and forbidden subgraphs -- a survey
- Weighted parameters in \((P_5,\overline {P_5})\)-free graphs
Cited in
(98)- Colouring of graphs with Ramsey-type forbidden subgraphs
- On the parameterized complexity of coloring graphs in the absence of a linear forest
- List homomorphism: beyond the known boundaries
- A New Characterization of P 6-Free Graphs
- \(H\)-colouring \(P_t\)-free graphs in subexponential time
- Algorithms and almost tight results for 3-colorability of small diameter graphs
- The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable
- Coloring problems on bipartite graphs of small diameter
- Better 3-coloring algorithms: excluding a triangle and a seven vertex path
- Solving problems on generalized convex graphs via mim-width
- Closing complexity gaps for coloring problems on \(H\)-free graphs
- Vertex coloring of graphs with few obstructions
- Coloring graphs without short cycles and long induced paths
- On pseudocomplete coloring of graphs
- Connected vertex cover for \((sP_1+P_5)\)-free graphs
- \(k\)-critical graphs in \(P_5\)-free graphs
- Choosability of P 5-Free Graphs
- Colouring vertices of triangle-free graphs without forests
- Constructions of k-critical P₅-free graphs
- Colouring square-free graphs without long induced paths
- Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
- A complete classification of the complexity of the vertex 3-colourability problem for quadruples of induced 5-vertex prohibitions
- scientific article; zbMATH DE number 7525468 (Why is no real title available?)
- Coloring graphs without short cycles and long induced paths
- Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes
- scientific article; zbMATH DE number 7651174 (Why is no real title available?)
- Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs
- Independent feedback vertex set for \(P_5\)-free graphs
- Updating the complexity status of coloring graphs without a fixed induced linear forest
- A survey on the computational complexity of coloring graphs with forbidden subgraphs
- Domination, coloring and stability in \(P_5\)-reducible graphs
- Colouring H-free graphs of bounded diameter.
- On algorithmic applications of sim-width and mim-width of \((H_1,H_2)\)-free graphs
- A refinement on the structure of vertex-critical \((P_5, \mathrm{gem})\)-free graphs
- Three-coloring and list three-coloring of graphs without induced paths on seven vertices
- 4-coloring \((P_6, \text{bull})\)-free graphs
- Stable sets in \(k\)-colorable \(P_{5}\)-free graphs
- Certifying coloring algorithms for graphs without long induced paths
- List 3-coloring on comb-convex and caterpillar-convex bipartite graphs
- Complexity of \(C_k\)-coloring in hereditary classes of graphs
- A new characterization of P_k-free graphs
- On list \(k\)-coloring convex bipartite graphs
- An intractability result for the vertex 3-colourability problem
- A Note on k-Colorability of P 5-Free Graphs
- Some results on graphs without long induced paths
- On \(r\)-hued colorings of graphs without short induced paths
- Colouring \((P_r + P_s)\)-free graphs
- List 3-coloring \(P_t\)-free graphs with no induced 1-subdivision of \(K_{1 , s}\)
- List k-colouring P_t-free graphs: a mim-width perspective
- Critical \((P_5,\mathit{dart})\)-free graphs
- List coloring in the absence of a linear forest
- Independent Feedback Vertex Set for P_5-free Graphs
- Colouring square-free graphs without long induced paths
- 3-colouring AT-free graphs in polynomial time
- Complete complexity dichotomy for 7-edge forbidden subgraphs in the edge coloring problem
- List coloring in the absence of a linear forest
- Solving problems on generalized convex graphs via mim-width
- The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs
- Colouring vertices of triangle-free graphs
- Partitioning Graphs into Connected Parts
- 4-colorability of P₆-free graphs
- On some domination colorings of graphs
- On the complexity of the vertex 3-coloring problem for the hereditary graph classes with forbidden subgraphs of small size
- Data reduction for graph coloring problems
- Colouring (P_r+P_s)-Free Graphs
- Coloring of pseudocubic graphs in three colors
- Cops and Robbers on \(\boldsymbol{P_5}\)-Free Graphs
- Near optimal colourability on hereditary graph families
- Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter
- Complexity of coloring graphs without paths and cycles
- On color-critical (\(P_5\),\(\operatorname{co-}P_5\))-free graphs
- Determining the chromatic number of triangle-free 2P₃-free graphs in polynomial time
- Connected greedy coloring of H-free graphs
- 4-coloring \(H\)-free graphs when \(H\) is small
- List-3-coloring ordered graphs with a forbidden induced subgraphs
- A complete complexity dichotomy of the edge-coloring problem for all sets of 8-edge forbidden subgraphs
- Complexity dichotomy for list-5-coloring with a forbidden induced subgraph
- 4‐Coloring P 6 ‐Free Graphs with No Induced 5‐Cycles
- \(k\)-critical graphs in \(P_5\)-free graphs
- On 3-coloring of \((2P_4,C_5)\)-free graphs
- On 3-coloring of \((2P_4,C_5)\)-free graphs
- Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
- Covering minimal separators and potential maximal cliques in \(P_t\)-free graphs
- Two complexity results for the vertex coloring problem
- Classifying \(k\)-edge colouring for \(H\)-free graphs
- 3-colouring \(P_t\)-free graphs without short odd cycles
- The complexity of coloring graphs without long induced paths
- Two cases of polynomial-time solvability for the coloring problem
- Polynomial cases for the vertex coloring problem
- A certifying algorithm for 3-colorability of \(P _{5}\)-free graphs
- Infinite families of \(k\)-vertex-critical \((P_5, C_5)\)-free graphs
- Four-Coloring \(P_6\)-Free Graphs. I. Extending an Excellent Precoloring
- Four-Coloring \(\boldsymbol{P_6}\)-Free Graphs. II. Finding an Excellent Precoloring
- On coloring a class of claw-free and hole-twin-free graphs
- Fundamentals of Computation Theory
- Vertex-critical \(( P_3 + \ell P_1 )\)-free and vertex-critical (gem, co-gem)-free graphs
- On 3-colorable \(P_5\)-free graphs
- Deciding \(k\)-colorability in expected polynomial time
This page was built for publication: Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q848637)
