Achromatic number is NP-complete for cographs and interval graphs
From MaRDI portal
Publication:1825646
DOI10.1016/0020-0190(89)90221-4zbMath0684.68046OpenAlexW2160875590WikidataQ56390758 ScholiaQ56390758MaRDI QIDQ1825646
Publication date: 1989
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://dspace.library.uu.nl/handle/1874/16576
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (36)
The Micro-world of Cographs ⋮ The micro-world of cographs ⋮ Harmonious coloring: parameterized algorithms and upper bounds ⋮ Harmonious Coloring: Parameterized Algorithms and Upper Bounds ⋮ On the \(b\)-continuity property of graphs ⋮ On the Pseudo-achromatic Number Problem ⋮ Homomorphically full graphs ⋮ Achromatic number of collections of paths and cycles ⋮ Bounds for the \(b\)-chromatic number of \(G-v\) ⋮ MSOL partitioning problems on graphs of bounded treewidth and clique-width ⋮ On the Grundy number of Cameron graphs ⋮ Generalising the achromatic number to Zaslavsky's colourings of signed graphs ⋮ Complete edge-colored permutation graphs ⋮ Complexity of maximum cut on interval graphs ⋮ Acyclic and star colorings of cographs ⋮ On the achromatic number of signed graphs ⋮ Computing and counting longest paths on circular-arc graphs in polynomial time ⋮ The harmonious coloring problem is NP-complete for interval and permutation graphs ⋮ Minimum order of graphs with given coloring parameters ⋮ Restricted coloring problems on graphs with few \(P_4\)'s ⋮ Complete partitions of graphs ⋮ On retracts, absolute retracts, and foldings in cographs ⋮ Paths in interval graphs and circular arc graphs ⋮ \(b\)-chromatic number of Cartesian product of some families of graphs ⋮ Achromatic number of fragmentable graphs ⋮ Efficient approximation algorithms for the achromatic number ⋮ Complete colourings of hypergraphs ⋮ VLSI layout of Benes networks ⋮ NP-completeness results for some problems on subclasses of bipartite and chordal graphs ⋮ On the pseudo-achromatic number problem ⋮ \(b\)-coloring is NP-hard on co-bipartite graphs and polytime solvable on tree-cographs ⋮ Linear-time algorithm for the matched-domination problem in cographs ⋮ The b-chromatic number of a graph ⋮ Restricted coloring problems on graphs with few ⋮ On the b-coloring of cographs and \(P_{4}\)-sparse graphs ⋮ On algorithms for (\(P_5\), gem)-free graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding Hamiltonian circuits in interval graphs
- Finding the minimum bandwidth of an interval graph
- Complement reducible graphs
- The NP-completeness column: an ongoing guide
- The edge inducibility of graphs
- Efficient algorithms for interval graphs and circular-arc graphs
- Total domination in interval graphs
- Total domination in interval graphs
This page was built for publication: Achromatic number is NP-complete for cographs and interval graphs
