scientific article; zbMATH DE number 2159638

zbMATH Open1059.05044arXivmath/0306178MaRDI QIDQ4667604FDOQ4667604

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

Publication date: 20 April 2005

Full work available at URL: https://arxiv.org/abs/math/0306178

Title of this publication is not available (Why is that?)

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

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)

Cited In (10)

• Graph partitions with prescribed patterns
• Generalized coloring of permutations
• Generalized Coloring of Permutations
• Inductive graph invariants and approximation algorithms
• Title not available (Why is that?)
• Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard
• Stable-\(\Pi\) partitions of graphs
• Minimization and parameterized variants of vertex partition problems on graphs
• Coloring graphs using two colors while avoiding monochromatic cycles
• Title not available (Why is that?)

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)