The P versus NP-complete dichotomy of some challenging problems in graph theory (Q1759844): Difference between revisions

@@ Property / DOI @@
-.1016/j.dam.2010.12.014
@@ Property / DOI: 10.1016/j.dam.2010.12.014 / rank @@
-Normal rank
@@ Property / author @@
+Celina M. Herrera de Figueiredo
@@ Property / author: Celina M. Herrera de Figueiredo / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/j.dam.2010.12.014
+Normal rank
@@ Property / OpenAlex ID @@
+W1971556138
@@ Property / OpenAlex ID: W1971556138 / rank @@
+Normal rank
@@ Property / cites work @@
+Cliques and extended triangles. A necessary condition for planar clique graphs
+Normal rank
@@ Property / cites work @@
+The complexity of clique graph recognition
@@ Property / cites work: The complexity of clique graph recognition / rank @@
+Normal rank
@@ Property / cites work @@
+A linear-time algorithm for testing the truth of certain quantified Boolean formulas
+Normal rank
@@ Property / cites work @@
+Q4489142
@@ Property / cites work: Q4489142 / rank @@
+Normal rank
@@ Property / cites work @@
+Topics on perfect graphs
@@ Property / cites work: Topics on perfect graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Partitions of graphs into one or two independent sets and cliques
+Normal rank
@@ Property / cites work @@
+The complexity of some problems related to GRAPH 3-COLORABILITY
+Normal rank
@@ Property / cites work @@
+On stable cutsets in graphs
@@ Property / cites work: On stable cutsets in graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Graph Classes: A Survey
@@ Property / cites work: Graph Classes: A Survey / rank @@
+Normal rank
@@ Property / cites work @@
+The Complexity of the List Partition Problem for Graphs
+Normal rank
@@ Property / cites work @@
+The homogeneous set sandwich problem
@@ Property / cites work: The homogeneous set sandwich problem / rank @@
+Normal rank
@@ Property / cites work @@
+Q4697576
@@ Property / cites work: Q4697576 / rank @@
+Normal rank
@@ Property / cites work @@
+Critical star multigraphs
@@ Property / cites work: Critical star multigraphs / rank @@
+Normal rank
@@ Property / cites work @@
+Recognizing Berge graphs
@@ Property / cites work: Recognizing Berge graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Berge trigraphs
@@ Property / cites work: Berge trigraphs / rank @@
+Normal rank
@@ Property / cites work @@
+The strong perfect graph theorem
@@ Property / cites work: The strong perfect graph theorem / rank @@
+Normal rank
@@ Property / cites work @@
+Star-cutsets and perfect graphs
@@ Property / cites work: Star-cutsets and perfect graphs / rank @@
+Normal rank
@@ Property / cites work @@
+\(2K_{2}\) vertex-set partition into nonempty parts
+Normal rank
@@ Property / cites work @@
+Decomposition of Directed Graphs
@@ Property / cites work: Decomposition of Directed Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+On decision and optimization (\(k\),\(l\))-graph sandwich problems
+Normal rank
@@ Property / cites work @@
+Finding<i>H</i>-partitions efficiently
@@ Property / cites work: Finding<i>H</i>-partitions efficiently / rank @@
+Normal rank
@@ Property / cites work @@
+List Partitions
@@ Property / cites work: List Partitions / rank @@
+Normal rank
@@ Property / cites work @@
+On edge-colouring indifference graphs
@@ Property / cites work: On edge-colouring indifference graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Q4487452
@@ Property / cites work: Q4487452 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4521527
@@ Property / cites work: Q4521527 / rank @@
+Normal rank
@@ Property / cites work @@
+The graph sandwich problem for 1-join composition is NP-complete
+Normal rank
@@ Property / cites work @@
+On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs
+Normal rank
@@ Property / cites work @@
+Q4198056
@@ Property / cites work: Q4198056 / rank @@
+Normal rank
@@ Property / cites work @@
+Graph Sandwich Problems
@@ Property / cites work: Graph Sandwich Problems / rank @@
+Normal rank
@@ Property / cites work @@
+Q3839009
@@ Property / cites work: Q3839009 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5749319
@@ Property / cites work: Q5749319 / rank @@
+Normal rank
@@ Property / cites work @@
+A partial characterization of clique graphs
@@ Property / cites work: A partial characterization of clique graphs / rank @@
+Normal rank
@@ Property / cites work @@
+The chromatic index of complete multipartite graphs
+Normal rank
@@ Property / cites work @@
+The NP-Completeness of Edge-Coloring
@@ Property / cites work: The NP-Completeness of Edge-Coloring / rank @@
+Normal rank
@@ Property / cites work @@
+The NP-completeness column: an ongoing guide
@@ Property / cites work: The NP-completeness column: an ongoing guide / rank @@
+Normal rank
@@ Property / cites work @@
+Fast Skew Partition Recognition
@@ Property / cites work: Fast Skew Partition Recognition / rank @@
+Normal rank
@@ Property / cites work @@
+Q4393307
@@ Property / cites work: Q4393307 / rank @@
+Normal rank
@@ Property / cites work @@
+Chromatic index of graphs with no cycle with a unique chord
+Normal rank
@@ Property / cites work @@
+Total chromatic number of {square,unichord}-free graphs
+Normal rank
@@ Property / cites work @@
+Topics in Intersection Graph Theory
@@ Property / cites work: Topics in Intersection Graph Theory / rank @@
+Normal rank
@@ Property / cites work @@
+On clique-complete graphs
@@ Property / cites work: On clique-complete graphs / rank @@
+Normal rank
@@ Property / cites work @@
+How to find overfull subgraphs in graphs with large maximum degree. II
+Normal rank
@@ Property / cites work @@
+Characterizing and edge-colouring split-indifference graphs
+Normal rank
@@ Property / cites work @@
+Q3221403
@@ Property / cites work: Q3221403 / rank @@
+Normal rank
@@ Property / cites work @@
+Distances and diameters on iterated clique graphs
@@ Property / cites work: Distances and diameters on iterated clique graphs / rank @@
+Normal rank
@@ Property / cites work @@
+The chromatic index of graphs with a spanning star
+Normal rank
@@ Property / cites work @@
+Q4288086
@@ Property / cites work: Q4288086 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4867717
@@ Property / cites work: Q4867717 / rank @@
+Normal rank
@@ Property / cites work @@
+Clique-inverse graphs ofK3-free andK4-free graphs
@@ Property / cites work: Clique-inverse graphs ofK3-free andK4-free graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Q4484907
@@ Property / cites work: Q4484907 / rank @@
+Normal rank
@@ Property / cites work @@
+Vertex colouring and forbidden subgraphs -- a survey
+Normal rank
@@ Property / cites work @@
+Skew partitions in perfect graphs
@@ Property / cites work: Skew partitions in perfect graphs / rank @@
+Normal rank
@@ Property / cites work @@
+A characterization of clique graphs
@@ Property / cites work: A characterization of clique graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Edge-colouring of join graphs
@@ Property / cites work: Edge-colouring of join graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Edge-colouring of regular graphs of large degree
@@ Property / cites work: Edge-colouring of regular graphs of large degree / rank @@
+Normal rank
@@ Property / cites work @@
+Efficient graph representations
@@ Property / cites work: Efficient graph representations / rank @@
+Normal rank
@@ Property / cites work @@
+Classification and characterizations of snarks
@@ Property / cites work: Classification and characterizations of snarks / rank @@
+Normal rank
@@ Property / cites work @@
+Chordal bipartite completion of colored graphs
@@ Property / cites work: Chordal bipartite completion of colored graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Clique Graphs of Chordal and Path Graphs
@@ Property / cites work: Clique Graphs of Chordal and Path Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Q4940014
@@ Property / cites work: Q4940014 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4407448
@@ Property / cites work: Q4407448 / rank @@
+Normal rank
@@ Property / cites work @@
+The sandwich problem for cutsets: clique cutset, \(k\)-star cutset
+Normal rank
@@ Property / cites work @@
+The polynomial dichotomy for three nonempty part sandwich problems
+Normal rank
@@ Property / cites work @@
+The external constraint 4 nonempty part sandwich problem
+Normal rank
@@ Property / cites work @@
+Skew partition sandwich problem is NP-complete
@@ Property / cites work: Skew partition sandwich problem is NP-complete / rank @@
+Normal rank
@@ Property / cites work @@
+A structure theorem for graphs with no cycle with a unique chord and its consequences
+Normal rank
@@ Property / DOI @@
+.1016/J.DAM.2010.12.014
@@ Property / DOI: 10.1016/J.DAM.2010.12.014 / rank @@
+Normal rank