On the Pseudo-achromatic Number Problem

DOI10.1007/978-3-540-92248-3_8MaRDI QIDQ5302045zbMATH OpenOpenAlexFDO

Authors Jie Meng, Ge Xia, Fenghui Zhang, Jianer Chen, Iyad Kanj

Publication date 20 January 2009

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://via.library.depaul.edu/cgi/viewcontent.cgi?article=1005&context=tr

zbMATH Keywords

fixed-parameter tractabilitykernelparameterized complexitypseudo-achromatic number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the pseudo-achromatic number problem
• The pseudoachromatic number of a graph
• On pseudoachromatic number of graphs
• On the parameterized complexity of the maximum edge 2-coloring problem
• Data reduction for graph coloring problems

Cites work

• Achromatic number is NP-complete for cographs and interval graphs
• Complete partitions of graphs
• scientific article; zbMATH DE number 1341905 (Why is no real title available?)
• scientific article; zbMATH DE number 475586 (Why is no real title available?)
• scientific article; zbMATH DE number 1874447 (Why is no real title available?)
• scientific article; zbMATH DE number 3334007 (Why is no real title available?)
• Introduction to algorithms
• On the pseudo-achromatic number problem
• On the pseudoachromatic number of a graph
• On the pseudoachromatic number of join of graphs
• Partition graphs and coloring numbers of a graph
• Strong computational lower bounds via parameterized complexity
• The complexity of harmonious colouring for trees
• The pseudoachromatic number of a graph

Cited in

(2)

• On the pseudo-achromatic number problem
• On upper bounds for the pseudo-achromatic index

This page was built for publication: On the Pseudo-achromatic Number Problem

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