The complexity of some problems related to GRAPH 3-COLORABILITY
From MaRDI portal
Publication:1281385
DOI10.1016/S0166-218X(98)00116-4zbMath0927.68063OpenAlexW2050157065MaRDI QIDQ1281385
Thomas Szymczak, Andreas Brandstädt, Van Bang Le
Publication date: 22 March 1999
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0166-218x(98)00116-4
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)
Related Items
On decision and optimization (\(k\),\(l\))-graph sandwich problems, Structural characterization and decomposition for cographs-(2, 1) and (1, 2): a natural generalization of threshold graphs, On equistable, split, CIS, and related classes of graphs, A note on the computational complexity of graph vertex partition, Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs, Characterizations, probe and sandwich problems on \(( k , \ell )\)-cographs, Independent feedback vertex sets for graphs of bounded diameter, The \((k, \ell)\) partitioned probe problem: NP-complete versus polynomial dichotomy, Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration, Characterization and recognition of \(P_{4}\)-sparse graphs partitionable into \(k\) independent sets and \(\ell \) cliques, Splitting a graph into disjoint induced paths or cycles., Partitioning extended \(P_4\)-laden graphs into cliques and stable sets, Sparse Graphs Are Near-Bipartite, Edge clique partition in \((k,\ell)\)-graphs, Stable-\(\Pi\) partitions of graphs, The P versus NP-complete dichotomy of some challenging problems in graph theory, Partition the vertices of a graph into one independent set and one acyclic set, On split-coloring problems, Acyclic, star, and injective colouring: bounding the diameter, On the Complexity of Probe and Sandwich Problems for Generalized Threshold Graphs, Partitioning chordal graphs into independent sets and cliques, Recognizing Graphs Close to Bipartite Graphs, Partitioning graphs into complete and empty graphs, Partitioning cographs into cliques and stable sets, Bisplit graphs, Characterizing –partitionable Cographs, Packing \(r\)-cliques in weighted chordal graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The splittance of a graph
- The ellipsoid method and its consequences in combinatorial optimization
- Some simplified NP-complete graph problems
- On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
- Threshold graphs and related topics
- Partitions of graphs into one or two independent sets and cliques
- The Complexity of Near-Optimal Graph Coloring
- A generalization of perfect graphs?i-perfect graphs
- The complexity of satisfiability problems
