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

DOI10.1016/j.dam.2010.12.014zbMath1253.68268OpenAlexW1971556138MaRDI 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 algorithmsgraph algorithmsproblem complexitystructural characterization of types of graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

Split clique graph complexity ⋮ Disconnected cuts in claw-free graphs ⋮ Hamiltonian Cycle in K1,r-Free Split Graphs — A Dichotomy ⋮ Unnamed Item ⋮ Hamiltonicity in Split Graphs - A Dichotomy ⋮ The computational complexity of disconnected cut and \(2 K_2\)-partition ⋮ Graph partitions with prescribed patterns

Cites Work

• 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
• Clique-inverse graphs ofK3-free andK4-free graphs
• 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
• 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