Imagen de Portada

The proper conflict-free $k$-coloring problem and the odd $k$-coloring problem are NP-complete on bipartite graphs

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Ahn, Jungho, Im, Seonghyuk, Oum, Sang-il
Formato:	Preprint
Publicado:	2022
Materias:	Computational Complexity Combinatorics 05C15, 68Q17
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

On 3-colorability of (claw, diamond)-free graphs
por: Hodur, Nadzieja, et al.
Publicado: (2026)

Quantum computing algorithms for inverse problems on graphs and an NP-complete inverse problem
por: Ilmavirta, Joonas, et al.
Publicado: (2023)

Results on three problems on isolation of graphs
por: Borg, Peter, et al.
Publicado: (2026)

The Separation of $NP$ and $PSPACE$
por: Lin, Tianrong
Publicado: (2021)

A Study of NP-Completeness and Undecidable Word Problems in Semigroups
por: Abdullah, Duaa, et al.
Publicado: (2025)

$k$-edge geodetic graphs
por: Guragain, Satyam, et al.
Publicado: (2024)

The n-vehicle exploration problem is NP-complete
por: Cui, Jinchuan, et al.
Publicado: (2023)

Friends-and-strangers is PSPACE-complete
por: Yang, Chao, et al.
Publicado: (2024)

Paintbucket on graphs is PSPACE-complete
por: Saunders, Ethan J., et al.
Publicado: (2024)

Toward P vs NP: An Observer-Theoretic Separation via SPDP Rank and a ZFC-Equivalent Foundation within the N-Frame Model
por: Edwards, Darren J.
Publicado: (2025)

An NP-hardness result for the colored constrained maximum 2-edge-colorable subgraph problem in bipartite graphs
por: Mkrtchyan, Vahan
Publicado: (2024)

Evolomino is NP-complete
por: Nikolaev, Andrei V.
Publicado: (2025)

Boundedness for proper conflict-free and odd colorings
por: Jiménez, Andrea, et al.
Publicado: (2023)

Complexity of chess domination problems
por: Langlois-Rémillard, Alexis, et al.
Publicado: (2022)

Polynomial Identity Testing via Evaluation of Rational Functions
por: Hu, Ivan, et al.
Publicado: (2022)

Generalisations of Matrix Partitions : Complexity and Obstructions
por: Barsukov, Alexey, et al.
Publicado: (2021)

Results on proper conflict-free list coloring of graphs
por: Kashima, Masaki, et al.
Publicado: (2025)

Mutual-visibility Coloring of Graphs
por: Babu, Saneesh, et al.
Publicado: (2025)

P not equal to NP
por: Delgado, Daniel Cardona
Publicado: (2023)

Probabilistic Computers (So Quantum Computers) Are More Rigorously Powerful Than Traditional Computers, and Derandomization
por: Lin, Tianrong
Publicado: (2023)

Flexible constraint satisfiability and a problem in semigroup theory
por: Jackson, Marcel
Publicado: (2015)

Degree-choosability of proper conflict-free list coloring of sparse graphs
por: Kashima, Masaki, et al.
Publicado: (2026)

Beyond the Existential Theory of the Reals
por: Schaefer, Marcus, et al.
Publicado: (2022)

Completeness classes in algebraic complexity theory
por: Bürgisser, Peter
Publicado: (2024)

The central tree property and algorithmic problems on subgroups of free groups
por: Roy, Mallika, et al.
Publicado: (2023)

NP-hard problems are not in BQP
por: Czerwinski, Reiner
Publicado: (2023)

Vanishing of Schubert Coefficients
por: Pak, Igor, et al.
Publicado: (2024)

Positivity of Schubert Coefficients
por: Pak, Igor, et al.
Publicado: (2024)

Hamiltonicity Parameterized by Mim-Width is (Indeed) Para-NP-Hard
por: Bergougnoux, Benjamin, et al.
Publicado: (2025)

Graph polynomials: some questions on the edge
por: Farr, Graham, et al.
Publicado: (2024)

On the 3-colorability of triangle-free and fork-free graphs
por: Schroeder, Joshua, et al.
Publicado: (2021)

Resolution of The Linear-Bounded Automata Question
por: Lin, Tianrong
Publicado: (2021)

Diagonalization of Polynomial-Time Deterministic Turing Machines via Nondeterministic Turing Machines
por: Lin, Tianrong
Publicado: (2021)

The antiferromagnetic Ising model beyond line graphs
por: Jerrum, Mark
Publicado: (2026)

Unifying lower bounds for algebraic machines, semantically
por: Seiller, Thomas, et al.
Publicado: (2018)

Vanishing of Schubert coefficients is in ${\sf AM}\cap {\sf coAM}$ assuming the GRH
por: Pak, Igor, et al.
Publicado: (2025)

Vanishing of Schubert coefficients in probabilistic polynomial time
por: Pak, Igor, et al.
Publicado: (2025)

Minor Embedding in Broken Chimera and Pegasus Graphs is NP-complete
por: Lobe, Elisabeth, et al.
Publicado: (2021)

The recording tableaux in the quantum Littlewood-Richardson map, the orthogonal transpose symmetry map, and the computation of $\mathfrak{k}$-highest weight tableaux
por: Azenhas, Olga
Publicado: (2026)

Simple Combinatorial Construction of the $k^{o(1)}$-Lower Bound for Approximating the Parameterized $k$-Clique
por: Chen, Yijia, et al.
Publicado: (2023)