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

zbMATH Open1204.68101MaRDI QIDQ3070909FDOQ3070909

Authors: Jérôme Monnot 

Publication date: 28 January 2011

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

Mathematics Subject Classification ID

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

Cited In (7)

• Precoloring extension. I: Interval graphs
• Hard coloring problems in low degree planar bipartite graphs
• NP completeness of the edge precoloring extension problem on bipartite 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
• \(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)