NP-completeness results for some problems on subclasses of bipartite and chordal graphs

DOI10.1016/j.tcs.2007.05.012zbMath1188.68208OpenAlexW2007549941MaRDI QIDQ995581

Stavros D. Nikolopoulos, Katerina Asdre

Publication date: 3 September 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.05.012

zbMATH Keywords

NP-completenessthreshold graphsconvex graphsharmonious coloringquasi-threshold graphsbipartite permutation graphs\(k\)-path partitionpair-complete coloring

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items

The micro-world of cographs, Harmonious coloring: parameterized algorithms and upper bounds, Harmonious Coloring: Parameterized Algorithms and Upper Bounds, Critical properties of bipartite permutation graphs, Canonical antichains of unit interval and bipartite permutation graphs, Minimal classes of graphs of unbounded clique-width, The harmonious coloring problem is NP-complete for interval and permutation graphs, Harmonious colourings of graphs, Star Partitions of Perfect Graphs, Linear-time algorithm for the paired-domination problem in convex bipartite graphs, A boundary class for the \(k\)-path partition problem, Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Recognizing cographs and threshold graphs through a classification of their edges
• Concerning the achromatic number of graphs
• Bipartite permutation graphs
• Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
• Some complexity results about threshold graphs
• The complexity of harmonious colouring for trees
• \(k\)-path partitions in trees
• On the \(k\)-path partition of graphs.
• Achromatic number is NP-complete for cographs and interval graphs
• Parallel algorithms for Hamiltonian problems on quasi-threshold graphs
• The harmonious coloring problem is NP-complete for interval and permutation graphs
• On the Harmonious Coloring of Graphs
• Edge Dominating Sets in Graphs
• Graph Classes: A Survey
• The achromatic number of a graph