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