4-coloring H-free graphs when H is small

Recommendations

4-coloring \(H\)-free graphs when \(H\) is small
Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs
Closing complexity gaps for coloring problems on \(H\)-free graphs
Improved complexity results on \(k\)-coloring \(P _{t }\)-free graphs
Updating the complexity status of coloring graphs without a fixed induced linear forest

Cites work

scientific article; zbMATH DE number 3882470 (Why is no real title available?)
scientific article; zbMATH DE number 2044943 (Why is no real title available?)
scientific article; zbMATH DE number 5179133 (Why is no real title available?)
3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
A New Algorithm for Generating All the Maximal Independent Sets
A certifying algorithm for 3-colorability of \(P _{5}\)-free graphs
Coloring edges and vertices of graphs without short or long cycles
Coloring graphs without short cycles and long induced paths
Colouring vertices of triangle-free graphs
Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
Determining the chromatic number of triangle-free 2P₃-free graphs in polynomial time
Graph colorings with local constraints -- a survey
List coloring in the absence of a linear forest
NP completeness of finding the chromatic index of regular graphs
On graphs with polynomially solvable maximum-weight clique problem
On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
On the complexity of 4-coloring graphs without long induced paths
Some new hereditary classes where graph coloring remains NP-hard
The NP-Completeness of Edge-Coloring
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
Updating the complexity status of coloring graphs without a fixed induced linear forest
Vertex colouring and forbidden subgraphs -- a survey

Cited in

(12)

On the parameterized complexity of coloring graphs in the absence of a linear forest
Closing complexity gaps for coloring problems on \(H\)-free graphs
Coloring graphs characterized by a forbidden subgraph
4-coloring \((P_6, \text{bull})\)-free graphs
\((2P_2,K_4)\)-free graphs are 4-colorable
Obstructions for three-coloring and list three-coloring \(H\)-free graphs
4-coloring \(H\)-free graphs when \(H\) is small
List coloring in the absence of a linear forest
List coloring in the absence of a linear forest
Choosability on \(H\)-free graphs
Connected greedy coloring of H-free graphs
On 3-coloring of \((2P_4,C_5)\)-free graphs

This page was built for publication: 4-coloring \(H\)-free graphs when \(H\) is small

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2891376)