The P versus NP-complete dichotomy of some challenging problems in graph theory
type: Item
instance of: scholarly article
title: The P versus NP-complete dichotomy of some challenging problems in graph theory
zbMATH Open document ID: 1253.68268
published in: Discrete Applied Mathematics
publication date: 2012-11-22T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W40
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C62
zbMATH DE Number: 6109915
zbMATH Keywords: analysis of algorithms
zbMATH Keywords: problem complexity
zbMATH Keywords: graph algorithms
zbMATH Keywords: structural characterization of types of graphs
author: Celina M. H. de Figueiredo
MaRDI profile type: Publication
full work available at URL: j.dam.2010.12.014
OpenAlex ID: W1971556138
cites work: Cliques and extended triangles. A necessary condition for planar clique graphs
cites work: The complexity of clique graph recognition
cites work: A linear-time algorithm for testing the truth of certain quantified Boolean formulas
cites work: Q4489142
cites work: Topics on perfect graphs
cites work: Partitions of graphs into one or two independent sets and cliques
cites work: The complexity of some problems related to GRAPH 3-COLORABILITY
cites work: On stable cutsets in graphs
cites work: Graph Classes: A Survey
cites work: The Complexity of the List Partition Problem for Graphs
cites work: The homogeneous set sandwich problem
cites work: Q4697576
cites work: Critical star multigraphs
cites work: Recognizing Berge graphs
cites work: Berge trigraphs
cites work: The strong perfect graph theorem
cites work: Star-cutsets and perfect graphs
cites work: \(2K_{2}\) vertex-set partition into nonempty parts
cites work: Decomposition of Directed Graphs
cites work: On decision and optimization (\(k\),\(l\))-graph sandwich problems
cites work: FindingH-partitions efficiently
cites work: List Partitions
cites work: On edge-colouring indifference graphs
cites work: Q4487452
cites work: Q4521527
cites work: The graph sandwich problem for 1-join composition is NP-complete
cites work: On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs
cites work: Q4198056
cites work: Graph Sandwich Problems
cites work: Q3839009
cites work: Q5749319
cites work: A partial characterization of clique graphs
cites work: The chromatic index of complete multipartite graphs
cites work: The NP-Completeness of Edge-Coloring
cites work: The NP-completeness column: an ongoing guide
cites work: Fast Skew Partition Recognition
cites work: Q4393307
cites work: Chromatic index of graphs with no cycle with a unique chord
cites work: Total chromatic number of \{square,unichord\}-free graphs
cites work: Topics in Intersection Graph Theory
cites work: On clique-complete graphs
cites work: How to find overfull subgraphs in graphs with large maximum degree. II
cites work: Characterizing and edge-colouring split-indifference graphs
cites work: Q3221403
cites work: Distances and diameters on iterated clique graphs
cites work: The chromatic index of graphs with a spanning star
cites work: Q4288086
cites work: Q4867717
cites work: Clique-inverse graphs ofK3-free andK4-free graphs
cites work: Q4484907
cites work: Vertex colouring and forbidden subgraphs -- a survey
cites work: Skew partitions in perfect graphs
cites work: A characterization of clique graphs
cites work: Edge-colouring of join graphs
cites work: Edge-colouring of regular graphs of large degree
cites work: Efficient graph representations
cites work: Classification and characterizations of snarks
cites work: Chordal bipartite completion of colored graphs
cites work: Clique Graphs of Chordal and Path Graphs

The P versus NP-complete dichotomy of some challenging problems in graph theory (cites work)
cites work: Q4940014

The P versus NP-complete dichotomy of some challenging problems in graph theory (cites work)
cites work: Q4407448

The P versus NP-complete dichotomy of some challenging problems in graph theory (cites work)
cites work: The sandwich problem for cutsets: clique cutset, \(k\)-star cutset

The P versus NP-complete dichotomy of some challenging problems in graph theory (cites work)
cites work: The polynomial dichotomy for three nonempty part sandwich problems

The P versus NP-complete dichotomy of some challenging problems in graph theory (cites work)
cites work: The external constraint 4 nonempty part sandwich problem

The P versus NP-complete dichotomy of some challenging problems in graph theory (cites work)
cites work: Skew partition sandwich problem is NP-complete

The P versus NP-complete dichotomy of some challenging problems in graph theory (cites work)
cites work: A structure theorem for graphs with no cycle with a unique chord and its consequences

The P versus NP-complete dichotomy of some challenging problems in graph theory (DOI)
DOI: 10.1016/J.DAM.2010.12.014