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

Redirect to:

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

DOI10.1016/J.DAM.2010.12.014MaRDI QIDQ1759844zbMATH OpenOpenAlexFDO

Authors Celina M. H. 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 algorithmsgraph algorithmsproblem complexitystructural characterization of types of graphs

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) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• The polynomial dichotomy for three nonempty part sandwich problems
• Complexity of graph partition problems
• The Complexity of the List Partition Problem for Graphs
• Complexity-separating graph classes for vertex, edge and total colouring
• On decision and optimization (\(k\),\(l\))-graph sandwich problems

Cites work

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

Cited in

(9)

• Split clique graph complexity
• Disconnected cuts in claw-free graphs
• Disconnected cuts in claw-free graphs
• Graph partitions with prescribed patterns
• The computational complexity of disconnected cut and \(2 K_2\)-partition
• Hamiltonicity in Split Graphs - A Dichotomy
• Solving a special case of the P conjecture using dependency graphs with dissolution
• The polynomial dichotomy for three nonempty part sandwich problems
• Hamiltonian Cycle in K1,r-Free Split Graphs — A Dichotomy

This page was built for publication: The P versus NP-complete dichotomy of some challenging problems in graph theory

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