The complexity of \(G\)-free colourability

DOI10.1016/S0012-365X(97)84217-3zbMath0904.05030MaRDI QIDQ1356726

Demetrios Achlioptas

Publication date: 5 November 1998

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

polynomial time algorithmchromatic numberNP-completebipartition2-colourable

Mathematics Subject Classification ID

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

Related Items (19)

Dynamic \(F\)-free coloring of graphs ⋮ Harary polynomials ⋮ Vertex partitioning problems on graphs with bounded tree width ⋮ On Symbolic Ultrametrics, Cotree Representations, and Cograph Edge Decompositions and Partitions ⋮ The existence of uniquely \(-G\) colourable graphs ⋮ Partitions of graphs into cographs ⋮ Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs ⋮ Inductive graph invariants and approximation algorithms ⋮ Co-bipartite neighborhood edge elimination orderings ⋮ Some bounds on the size of maximum G-free sets in graphs ⋮ Partitioning of a graph into induced subgraphs not containing prescribed cliques ⋮ Unnamed Item ⋮ Subcolorings and the subchromatic number of a graph ⋮ On the complexity of generalized chromatic polynomials ⋮ On tree representations of relations and graphs: symbolic ultrametrics and cograph edge decompositions ⋮ On 2-Subcolourings of Chordal Graphs ⋮ Solving Partition Problems Almost Always Requires Pushing Many Vertices Around ⋮ Unnamed Item ⋮ Vertex Partitions of Graphs into Cographs and Stars

Cites Work

• The existence of uniquely \(-G\) colourable graphs
• The point-arboricity of a graph
• On generalized graph colorings
• ON UNIQUELY -G k-COLOURABLE GRAPHS
• Graphs with unique Ramsey colorings
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The complexity of \(G\)-free colourability