The complexity of some problems related to GRAPH 3-COLORABILITY
From MaRDI portal
Publication:1281385
Recommendations
- A note on the computational complexity of graph vertex partition
- On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
- An intractability result for the vertex 3-colourability problem
- The 3-Colorability Problem on Graphs with Maximum Degree Four
- The NP-completeness of chromatic index in triangle free graphs with maximum vertex of degree 3
Cites work
- scientific article; zbMATH DE number 3882470 (Why is no real title available?)
- scientific article; zbMATH DE number 3503283 (Why is no real title available?)
- scientific article; zbMATH DE number 3571502 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- A generalization of perfect graphs?i-perfect graphs
- On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
- Partitions of graphs into one or two independent sets and cliques
- Some simplified NP-complete graph problems
- The Complexity of Near-Optimal Graph Coloring
- The complexity of satisfiability problems
- The ellipsoid method and its consequences in combinatorial optimization
- The splittance of a graph
- Threshold graphs and related topics
Cited in
(37)- Characterizing –partitionable Cographs
- On equistable, split, CIS, and related classes of graphs
- Recognizing Graphs Close to Bipartite Graphs
- Sparse graphs are near-bipartite
- Deciding 3-colourability in less than O(1.415n) steps
- Partition the vertices of a graph into one independent set and one acyclic set
- Bisplit graphs
- Constructive generation of very hard 3-colorability instances
- Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs
- The NP-completeness of (1,r)-subcolorability of cubic graphs
- Edge clique partition in \((k,\ell)\)-graphs
- Independent feedback vertex sets for graphs of bounded diameter
- The P versus NP-complete dichotomy of some challenging problems in graph theory
- Acyclic, star, and injective colouring: bounding the diameter
- On the complexity of probe and sandwich problems for generalized threshold graphs
- On decision and optimization (\(k\),\(l\))-graph sandwich problems
- On 3-hued coloring of graphs
- Near-bipartiteness, connected near-bipartiteness, independent feedback vertex set and acyclic vertex cover on graphs having small dominating sets
- Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration
- Partitioning extended \(P_4\)-laden graphs into cliques and stable sets
- The 3-Colorability Problem on Graphs with Maximum Degree Four
- Structural characterization and decomposition for cographs-(2, 1) and (1, 2): a natural generalization of threshold graphs
- Splitting a graph into disjoint induced paths or cycles.
- Characterization and recognition of \(P_{4}\)-sparse graphs partitionable into \(k\) independent sets and \(\ell \) cliques
- Some complexity results about threshold graphs
- On split-coloring problems
- Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs
- Partitioning chordal graphs into independent sets and cliques
- Stable-\(\Pi\) partitions of graphs
- Partitioning graphs into complete and empty graphs
- scientific article; zbMATH DE number 3913673 (Why is no real title available?)
- The \((k, \ell)\) partitioned probe problem: NP-complete versus polynomial dichotomy
- A note on the computational complexity of graph vertex partition
- Intersection of chordal graphs and some related partition problems
- Characterizations, probe and sandwich problems on \(( k , \ell )\)-cographs
- Packing \(r\)-cliques in weighted chordal graphs
- Partitioning cographs into cliques and stable sets
This page was built for publication: The complexity of some problems related to GRAPH 3-COLORABILITY
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1281385)
