A note on the NP-completeness of the precoloring extension coloring problem in triangle free planar graphs

MaRDI QIDQ3070909zbMATH OpenFDO

Authors Jérôme Monnot

Publication date 28 January 2011

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Hard coloring problems in low degree planar bipartite graphs
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• scientific article; zbMATH DE number 772747
• scientific article; zbMATH DE number 772760
• NP‐completeness of list coloring and precoloring extension on the edges of planar graphs

Cited in

(7)

• Precoloring extension. I: Interval graphs
• Precoloring extension on unit interval graphs
• NP‐completeness of list coloring and precoloring extension on the edges of planar graphs
• Precoloring extension for 2-connected graphs with maximum degree three
• NP completeness of the edge precoloring extension problem on bipartite graphs
• Hard coloring problems in low degree planar bipartite graphs
• \(L(2,1)\)-coloring of precolored cacti

This page was built for publication: A note on the NP-completeness of the precoloring extension coloring problem in triangle free planar graphs

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