The complexity of some problems related to GRAPH 3-COLORABILITY

DOI10.1016/S0166-218X(98)00116-4MaRDI QIDQ1281385zbMATH OpenOpenAlexFDO

Authors Andreas Brandstädt, Van Bang Le, Thomas Szymczak

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

zbMATH Keywords

graph 3-colorability problem

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

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

• A generalization of perfect graphs?i-perfect graphs
• 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?)
• 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

(39)

• Partitioning graphs into complete and empty graphs
• Some complexity results about threshold graphs
• Splitting a graph into disjoint induced paths or cycles.
• The NP-completeness of (1,r)-subcolorability of cubic graphs
• Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs
• Independent feedback vertex sets for graphs of bounded diameter
• The \((k, \ell)\) partitioned probe problem: NP-complete versus polynomial dichotomy
• The P versus NP-complete dichotomy of some challenging problems in graph theory
• Partitioning chordal graphs into independent sets and cliques
• On decision and optimization (\(k\),\(l\))-graph sandwich problems
• Characterizations, probe and sandwich problems on \(( k , \ell )\)-cographs
• Edge clique partition in \((k,\ell)\)-graphs
• Stable-\(\Pi\) partitions of graphs
• Constructive generation of very hard 3-colorability instances
• Partition the vertices of a graph into one independent set and one acyclic set
• Partitioning cographs into cliques and stable sets
• Bisplit graphs
• On the complexity of probe and sandwich problems for generalized threshold graphs
• On 3-hued coloring of graphs
• Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs
• Structural characterization and decomposition for cographs-(2, 1) and (1, 2): a natural generalization of threshold graphs
• Characterizing –partitionable Cographs
• On equistable, split, CIS, and related classes of graphs
• scientific article; zbMATH DE number 3913673 (Why is no real title available?)
• The 3-Colorability Problem on Graphs with Maximum Degree Four
• Partitioning extended \(P_4\)-laden graphs into cliques and stable sets
• Recognizing Graphs Close to Bipartite Graphs
• Sparse graphs are near-bipartite
• Acyclic, star, and injective colouring: bounding the diameter
• Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration
• Deciding 3-colourability in less than O(1.415n) steps
• Characterization and recognition of \(P_{4}\)-sparse graphs partitionable into \(k\) independent sets and \(\ell \) cliques
• Near-bipartiteness, connected near-bipartiteness, independent feedback vertex set and acyclic vertex cover on graphs having small dominating sets
• Intersection of chordal graphs and some related partition problems
• Near-bipartiteness on graphs having small dominating sets
• Word-representable co-bipartite graphs: representation number, speed, and entropy
• Packing \(r\)-cliques in weighted chordal graphs
• A note on the computational complexity of graph vertex partition
• On split-coloring problems

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)