Colouring vertices of triangle-free graphs
From MaRDI portal
Recommendations
- Colouring vertices of triangle-free graphs without forests
- On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
- Determining the chromatic number of triangle-free 2P₃-free graphs in polynomial time
- Coloring graphs characterized by a forbidden subgraph
- On coloring graphs without induced forests
Cites work
- 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
- 3-colorability and forbidden subgraphs. I: Characterizing pairs
- A 4-colour problem for dense triangle-free graphs
- A New Algorithm for Generating All the Maximal Independent Sets
- Bipartite graphs without a skew star
- Coloring edges and vertices of graphs without short or long cycles
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- scientific article; zbMATH DE number 1002021 (Why is no real title available?)
- scientific article; zbMATH DE number 2044943 (Why is no real title available?)
- scientific article; zbMATH DE number 1833071 (Why is no real title available?)
- scientific article; zbMATH DE number 2203240 (Why is no real title available?)
- scientific article; zbMATH DE number 5279372 (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 Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
- On the complexity of 4-coloring graphs without long induced paths
- On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
- Recent developments on graphs of bounded clique-width
- The 3-Colorability Problem on Graphs with Maximum Degree Four
- THE CLIQUE-WIDTH OF BIPARTITE GRAPHS IN MONOGENIC CLASSES
- The complexity of coloring graphs without long induced paths
- The NP-Completeness of Edge-Coloring
- Three complexity results on coloring \(P _{k }\)-free graphs
- Three-colourability and forbidden subgraphs. II: Polynomial algorithms
- Triangle-free graphs and forbidden subgraphs
- Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
- Upper bounds to the clique width of graphs
- Vertex colouring and forbidden subgraphs -- a survey
Cited in
(22)- On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
- Coloring triangle-free graphs with fixed size
- On vertex coloring without monochromatic triangles
- 4-coloring \(H\)-free graphs when \(H\) is small
- Greedy algorithms for triangle free coloring
- On 3-colouring of graphs with short faces and bounded maximum vertex degree
- Colouring diamond-free graphs
- A technique for multicoloring triangle-free hexagonal graphs
- 4-coloring \(H\)-free graphs when \(H\) is small
- Coloring graphs without short cycles and long induced paths
- List coloring in the absence of a linear forest
- On square-free vertex colorings of graphs
- Coloring of Triangle-Free Graphs on the Double Torus
- Determining the chromatic number of triangle-free 2P₃-free graphs in polynomial time
- On the parameterized complexity of coloring graphs in the absence of a linear forest
- Coloring (gem, co‐gem)‐free graphs
- scientific article; zbMATH DE number 7274066 (Why is no real title available?)
- Complexity of conditional colourings with given template
- Coloring Triangle-Free Graphs on Surfaces
- Adaptable and conflict colouring multigraphs with no cycles of length three or four
- Updating the complexity status of coloring graphs without a fixed induced linear forest
- Colouring vertices of triangle-free graphs without forests
This page was built for publication: Colouring vertices of triangle-free graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3057624)
