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



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