The P versus NP-complete dichotomy of some challenging problems in graph theory

DOI10.1016/j.dam.2010.12.014zbMath1253.68268MaRDI QIDQ1759844

Celina M. Herrera de Figueiredo

Publication date: 22 November 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2010.12.014

zbMATH Keywords

analysis of algorithms; graph algorithms; problem complexity; structural characterization of types of graphs

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W40: Analysis of algorithms

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

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

05C62: Graph representations (geometric and intersection representations, etc.)

Related Items

Split clique graph complexity, The computational complexity of disconnected cut and \(2 K_2\)-partition, Graph partitions with prescribed patterns, Hamiltonicity in Split Graphs - A Dichotomy

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The homogeneous set sandwich problem
• The external constraint 4 nonempty part sandwich problem
• Topics on perfect graphs
• The strong perfect graph theorem
• \(2K_{2}\) vertex-set partition into nonempty parts
• On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs
• The complexity of clique graph recognition
• Critical star multigraphs
• Star-cutsets and perfect graphs
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• The complexity of some problems related to GRAPH 3-COLORABILITY
• On clique-complete graphs
• Characterizing and edge-colouring split-indifference graphs
• On edge-colouring indifference graphs
• Efficient graph representations
• On stable cutsets in graphs
• Classification and characterizations of snarks
• How to find overfull subgraphs in graphs with large maximum degree. II
• The graph sandwich problem for 1-join composition is NP-complete
• Cliques and extended triangles. A necessary condition for planar clique graphs
• Distances and diameters on iterated clique graphs
• On decision and optimization (\(k\),\(l\))-graph sandwich problems
• Vertex colouring and forbidden subgraphs -- a survey
• Partitions of graphs into one or two independent sets and cliques
• Chromatic index of graphs with no cycle with a unique chord
• Edge-colouring of join graphs
• Chordal bipartite completion of colored graphs
• Edge-colouring of regular graphs of large degree
• Skew partitions in perfect graphs
• Recognizing Berge graphs
• The sandwich problem for cutsets: clique cutset, \(k\)-star cutset
• A characterization of clique graphs
• Skew partition sandwich problem is NP-complete
• Total chromatic number of {square,unichord}-free graphs
• The Complexity of the List Partition Problem for Graphs
• The NP-completeness column: an ongoing guide
• The chromatic index of graphs with a spanning star
• The NP-Completeness of Edge-Coloring
• Decomposition of Directed Graphs
• The chromatic index of complete multipartite graphs
• Topics in Intersection Graph Theory
• Graph Classes: A Survey
• Clique Graphs of Chordal and Path Graphs
• List Partitions
• FindingH-partitions efficiently
• Graph Sandwich Problems
• A structure theorem for graphs with no cycle with a unique chord and its consequences
• Fast Skew Partition Recognition
• Berge trigraphs
• A partial characterization of clique graphs
• The polynomial dichotomy for three nonempty part sandwich problems