Complexity of near-3-choosability problem

DOI10.1007/S00373-024-02837-XMaRDI QIDQ6632143zbMATH OpenFDO

Authors Sounaka Mishra, S. Rohini, Sagar S. Sawant

Publication date 4 November 2024

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S00373-024-02837-X

zbMATH Keywords

\(\mathbb{NP}\)-completenessapproximation algorithmgraph coloringlist coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• The complexity of planar graph choosability
• 3-choosability of planar graphs with \((\leqslant 4)\)-cycles far apart
• On 3-choosability of plane graphs having no 3-, 6-, 7- and 8-cycles
• Near-colorings: non-colorable graphs and NP-completeness
• 3-choosability of triangle-free planar graphs with constraints on 4-cycles

Cites work

• A not 3-choosable planar graph without 3-cycles
• A refinement of choosability of graphs
• A survey on the computational complexity of coloring graphs with forbidden subgraphs
• Additive approximation for edge-deletion problems
• Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Independent feedback vertex sets for graphs of bounded diameter
• Minimization and parameterized variants of vertex partition problems on graphs
• On \(t\)-common list-colorings
• Partition the vertices of a graph into one independent set and one acyclic set
• Planar Formulae and Their Uses
• Smaller planar triangle-free graphs that are not 3-list-colorable
• The complexity of planar graph choosability
• Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard

This page was built for publication: Complexity of near-3-choosability problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6632143)