Complexity of conditional colourings with given template

MaRDI QIDQ5167724zbMATH OpenFDO

Authors Peter Dukes, Steve Lowdon, Gary MacGillivray

Publication date 1 July 2014

Full work available at URL https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/2327/0.html

zbMATH Keywords

homomorphismgraph colouringvertex partitions

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Complexity of conditional colorability of graphs
• Generalized partitions of graphs
• The complexity of \(G\)-free colourability
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• Colouring vertices of triangle-free graphs

Cited in

(2)

• Complexity of conditional colorability of graphs
• Conditional Hardness for Approximate Coloring

This page was built for publication: Complexity of conditional colourings with given template

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