Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
From MaRDI portal
Publication:1146685
DOI10.1016/0012-365X(80)90236-8zbMath0448.05030WikidataQ55899212 ScholiaQ55899212MaRDI QIDQ1146685
Publication date: 1980
Published in: Discrete Mathematics (Search for Journal in Brave)
Related Items
Further extensions of the Grötzsch theorem, Star colouring of bounded degree graphs and regular graphs, On the Nash number and the diminishing Grundy number of a graph, As Time Goes By: Reflections on Treewidth for Temporal Graphs, HV-planarity: algorithms and complexity, An intractability result for the vertex 3-colourability problem, Coloring immersion-free graphs, On the computational complexity of defining sets, Non-existence of stable social groups in information-driven networks, On the Complexity of the Minimum Independent Set Partition Problem, Identifying influential nodes in complex networks: A node information dimension approach, Regular pattern-free coloring, List-coloring -- parameterizing from triviality, The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs, 3-coloring triangle-free planar graphs with a precolored 9-cycle, 3-Coloring Triangle-Free Planar Graphs with a Precolored 9-Cycle, Algorithmic complexity of proper labeling problems, Feedback vertex set on Hamiltonian graphs, Acyclic coloring with few division vertices, \(b\)-continuity and partial Grundy coloring of graphs with large girth, Topology optimization design of 3D electrothermomechanical actuators by using GPU as a co-processor, A topological lower bound for the chromatic number of a special family of graphs, Inductive graph invariants and approximation algorithms, 3-colouring AT-free graphs in polynomial time, PTAS for Sparse General-valued CSPs, Sudoku number of graphs, 5-list coloring toroidal 6-regular triangulations in linear time, The \((3, 3)\)-colorability of planar graphs without 4-cycles and 5-cycles, Hardness transitions and uniqueness of acyclic colouring, Unnamed Item, Proper colorability of segment intersection graphs, Dominating set based exact algorithms for \(3\)-coloring, On the parameterized complexity of clustering problems for incomplete data, Robust Factorizations and Colorings of Tensor Graphs, Unnamed Item, Finer Tight Bounds for Coloring on Clique-Width, Why Is Maximum Clique Often Easy in Practice?, CHECKCOL: improved local search for graph coloring, Efficient computation of the oriented chromatic number of recursively defined digraphs, Coloring graphs by iterated local search traversing feasible and infeasible solutions, Embedding a novel objective function in a two-phased local search for robust vertex coloring, Colouring Vertices of Triangle-Free Graphs, On 3-colouring of graphs with short faces and bounded maximum vertex degree, Vertex-Coloring with Star-Defects, Fixed-parameter tractability of \((n-k)\) list coloring, Homomorphism Reconfiguration via Homotopy, On the Complexity of the Vertex 3-Coloring Problem for the Hereditary Graph Classes With Forbidden Subgraphs of Small Size, Stable matching with uncertain linear preferences, Colouring vertices of triangle-free graphs without forests, Graph coloring with cardinality constraints on the neighborhoods, Graph coloring: a novel heuristic based on trailing path-properties, perspective and applications in structured networks, Role coloring bipartite graphs, Parameterized complexity of list coloring and max coloring, Domination, coloring and stability in \(P_5\)-reducible graphs, The computational complexity of the backbone coloring problem for planar graphs with connected backbones, Quantum graph homomorphisms via operator systems, On the maximum parsimony distance between phylogenetic trees
Cites Work
