Determining the chromatic number of triangle-free 2P₃-free graphs in polynomial time
From MaRDI portal
(Redirected from Publication:417995)
Determining the chromatic number of triangle-free \(2P 3\)-free graphs in polynomial time
Determining the chromatic number of triangle-free \(2P 3\)-free graphs in polynomial time
Recommendations
Cites work
- 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
- A certifying algorithm for 3-colorability of \(P _{5}\)-free graphs
- A New Algorithm for Generating All the Maximal Independent Sets
- Coloring edges and vertices of graphs without short or long cycles
- Colouring vertices of triangle-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 2044943 (Why is no real title available?)
- scientific article; zbMATH DE number 772747 (Why is no real title available?)
- scientific article; zbMATH DE number 5179133 (Why is no real title available?)
- Linear time solvable optimization problems on graphs of bounded clique-width
- On graphs with polynomially solvable maximum-weight clique problem
- On the complexity of 4-coloring graphs without long induced paths
- On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
- THE CLIQUE-WIDTH OF BIPARTITE GRAPHS IN MONOGENIC CLASSES
- The complexity of coloring graphs without long induced paths
- The complexity of colouring problems on dense graphs
- Three complexity results on coloring \(P _{k }\)-free graphs
- Triangle-free graphs and forbidden subgraphs
- Updating the complexity status of coloring graphs without a fixed induced linear forest
- Vertex colouring and forbidden subgraphs -- a survey
Cited in
(27)- On vertex coloring without monochromatic triangles
- On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs
- 4-coloring \(H\)-free graphs when \(H\) is small
- Sparse regular induced subgraphs in \(2P_3\)-free graphs
- Triangle-free 2P₃-free graphs are 4-colorable
- List coloring in the absence of a linear forest
- Colouring square-free graphs without long induced paths
- Colouring diamond-free graphs
- Coloring graphs without short cycles and long induced paths
- List coloring in the absence of two subgraphs
- 4-coloring \(H\)-free graphs when \(H\) is small
- Clique-width of graph classes defined by two forbidden induced subgraphs
- A survey on the computational complexity of coloring graphs with forbidden subgraphs
- Colouring vertices of triangle-free graphs
- On coloring graphs without induced forests
- Coloring graphs without short cycles and long induced paths
- List coloring in the absence of a linear forest
- Colouring square-free graphs without long induced paths
- Vertex coloring of graphs with few obstructions
- Colouring of graphs with Ramsey-type forbidden subgraphs
- On the parameterized complexity of coloring graphs in the absence of a linear forest
- A class of three-colorable triangle-free graphs
- On the power of threshold-based algorithms for detecting cycles in the \textsc{CONGEST} model
- On the power of threshold-based algorithms for detecting cycles in the CONGEST model
- Polynomial cases for the vertex coloring problem
- Maximum regular induced subgraphs in 2P₃-free graphs
- Updating the complexity status of coloring graphs without a fixed induced linear forest
This page was built for publication: Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q417995)
