A note on the complexity of the chromatic number problem
From MaRDI portal
Publication:1229753
DOI10.1016/0020-0190(76)90065-XzbMath0336.68021WikidataQ56269094 ScholiaQ56269094MaRDI QIDQ1229753
Publication date: 1976
Published in: Information Processing Letters (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Algorithms in computer science (68W99)
Related Items
Minimal Dominating Sets in Graph Classes: Combinatorial Bounds and Enumeration ⋮ The Number of Maximal Independent Sets in a Tree ⋮ Improved edge-coloring with three colors ⋮ Lower Bounds for the Graph Homomorphism Problem ⋮ On the Fine-Grained Complexity of Rainbow Coloring ⋮ Harmonious coloring: parameterized algorithms and upper bounds ⋮ An improved algorithm for approximating the chromatic number of \(G_{n,p}\) ⋮ An improved exact algorithm for the domatic number problem ⋮ Harmonious Coloring: Parameterized Algorithms and Upper Bounds ⋮ On the parameterized complexity of b-\textsc{chromatic number} ⋮ Efficient bounds on a branch and bound algorithm for graph colouration ⋮ Parameterized and exact algorithms for class domination coloring ⋮ Coloring, location and domination of corona graphs ⋮ Enumeration and maximum number of minimal connected vertex covers in graphs ⋮ Minimal dominating sets in graph classes: combinatorial bounds and enumeration ⋮ Unnamed Item ⋮ Vertex coloring of a graph for memory constrained scenarios ⋮ Enumeration of minimal tropical connected sets ⋮ A Moderately Exponential Time Algorithm for Full Degree Spanning Tree ⋮ Exact Algorithms for Edge Domination ⋮ An approximation algorithm for 3-Colourability ⋮ Deciding 3-colourability in less than O(1.415n) steps ⋮ Dominating set based exact algorithms for \(3\)-coloring ⋮ Sharp separation and applications to exact and parameterized algorithms ⋮ Exact algorithms for edge domination ⋮ On the hardness of inclusion-wise minimal separators enumeration ⋮ Parameterized and Exact Algorithms for Class Domination Coloring ⋮ Feedback Vertex Sets in Tournaments ⋮ Branch and recharge: exact algorithms for generalized domination ⋮ New plain-exponential time classes for graph homomorphism ⋮ New exact algorithms for the 2-constraint satisfaction problem ⋮ Trimmed Moebius inversion and graphs of bounded degree ⋮ An exact algorithm for the minimum dominating clique problem ⋮ Dual parameterization of Weighted Coloring ⋮ Invitation to Algorithmic Uses of Inclusion–Exclusion ⋮ The parameterized complexity of maximality and minimality problems ⋮ Open problems around exact algorithms ⋮ Complexity of Grundy coloring and its variants ⋮ Exact algorithms for exact satisfiability and number of perfect matchings ⋮ An exact algorithm for the channel assignment problem ⋮ Enumerating maximal independent sets with applications to graph colouring. ⋮ On the complexity of \(k\)-SAT ⋮ Graph theory (algorithmic, algebraic, and metric problems) ⋮ Improved algorithm to determine 3-colorability of graphs with minimum degree at least 7 ⋮ Efficiency in exponential time for domination-type problems ⋮ On the span in channel assignment problems: Bounds, computing and counting ⋮ Faster graph coloring in polynomial space ⋮ New Plain-Exponential Time Classes for Graph Homomorphism ⋮ Testing the Complexity of a Valued CSP Language ⋮ A note on coloring sparse random graphs ⋮ From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge between Graphs and Alternating Matrix Spaces ⋮ Exact algorithms for counting 3-colorings of graphs ⋮ Dual parameterization of weighted coloring ⋮ A new backtracking algorithm for generating the family of maximal independent sets of a graph ⋮ Tropical lower bound for extended formulations. II. Deficiency graphs of matrices ⋮ Moderate exponential-time algorithms for scheduling problems ⋮ Exponential-time quantum algorithms for graph coloring problems ⋮ The resolution complexity of random graph \(k\)-colorability ⋮ On maximum number of minimal dominating sets in graphs
Cites Work
- Unnamed Item
- Unnamed Item
- The Complexity of Near-Optimal Graph Coloring
- An Algorithm for Determining the Chromatic Number of a Graph
- An Algorithm for the Chromatic Number of a Graph
- An algorithm for the chromatic number of a graph
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- Corrections to Bierstone's Algorithm for Generating Cliques
- Chromatic Scheduling and the Chromatic Number Problem
