On the generic complexity of graph 3-coloring problems

MaRDI QIDQ6889544zbMATH OpenFDO

Authors D. P. Ruzanova, Alexander Rybalov

Publication date 4 December 2025

Published in Prikladnaya Diskretnaya Matematika (Search for Journal in Brave)

zbMATH Keywords

3-coloring of graphsgeneric complexity

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Cryptography (94A60)

Cites work

• Generic-case complexity, decision problems in group theory, and random walks.
• scientific article; zbMATH DE number 4101089 (Why is no real title available?)
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• On generic complexity of the discrete logarithm problem
• ON GENERIC COMPLEXITY OF THE PROBLEM OF FINDING ROOTS IN GROUPS OF RESIDUES
• ON GENERIC COMPLEXITY OF THE QUADRATIC RESIDUOSITY PROBLEM
• Reducibility among combinatorial problems

This page was built for publication: On the generic complexity of graph 3-coloring problems

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