4-coloring H-free graphs when H is small

DOI10.1007/978-3-642-27660-6_24zbMATH Open1298.05117OpenAlexW2180782402MaRDI QIDQ2891376FDOQ2891376

Authors: Petr A. Golovach, Daniël Paulusma, Jian Song 

Publication date: 15 June 2012

Published in: SOFSEM 2012: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-27660-6_24

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15)

Cites Work

• The complexity of colouring problems on dense graphs
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• Title not available (Why is that?)
• Three complexity results on coloring \(P _{k }\)-free graphs
• The NP-Completeness of Edge-Coloring
• A New Algorithm for Generating All the Maximal Independent Sets
• Title not available (Why is that?)
• Updating the complexity status of coloring graphs without a fixed induced linear forest
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• Graph colorings with local constraints -- a survey
• The complexity of coloring graphs without long induced paths
• Title not available (Why is that?)
• NP completeness of finding the chromatic index of regular graphs
• Vertex colouring and forbidden subgraphs -- a survey
• Coloring edges and vertices of graphs without short or long cycles
• On the complexity of 4-coloring graphs without long induced paths
• A certifying algorithm for 3-colorability of \(P _{5}\)-free graphs
• On graphs with polynomially solvable maximum-weight clique problem
• Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time
• Some new hereditary classes where graph coloring remains NP-hard
• List coloring in the absence of a linear forest
• Colouring vertices of triangle-free graphs
• Coloring graphs without short cycles and long induced paths

Cited In (11)

• 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

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)