scientific article; zbMATH DE number 2159638

MaRDI QIDQ4667604zbMATH OpenFDO

Authors Alastair Farrugia, V. E. Alekseev, Vadim Lozin

Publication date 20 April 2005

Full work available at URL https://arxiv.org/abs/math/0306178, https://eudml.org/doc/124356, http://www.emis.de/journals/DMTCS/volumes/abstracts/dm060204.abs.html

zbMATH Keywords

NP-completenessPolynomial algorithmGeneralized graph coloring

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard
• The complexity of generalized graph colorings
• Publication:4725766
• scientific article; zbMATH DE number 512918
• Some new hereditary classes where graph coloring remains NP-hard

Cited in

(10)

• Stable-\(\Pi\) partitions of graphs
• Coloring graphs using two colors while avoiding monochromatic cycles
• Generalized coloring of permutations
• Graph partitions with prescribed patterns
• scientific article; zbMATH DE number 3999312 (Why is no real title available?)
• Generalized Coloring of Permutations
• scientific article; zbMATH DE number 1751952 (Why is no real title available?)
• Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard
• Minimization and parameterized variants of vertex partition problems on graphs
• Inductive graph invariants and approximation algorithms

This page was built for publication:

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