Buchumschlag

Approximate Graph Colouring and the Crystal with a Hollow Shadow

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Ciardo, Lorenzo, Živný, Stanislav
Format:	Preprint
Veröffentlicht:	2022
Schlagworte:	Computational Complexity Discrete Mathematics Combinatorics Optimization and Control
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Hierarchies of Minion Tests for PCSPs through Tensors
von: Ciardo, Lorenzo, et al.
Veröffentlicht: (2022)

Semidefinite programming and linear equations vs. homomorphism problems
von: Ciardo, Lorenzo, et al.
Veröffentlicht: (2023)

The periodic structure of local consistency
von: Ciardo, Lorenzo, et al.
Veröffentlicht: (2024)

Diffusion-Robust Optimization over Graphs
von: Aolaritei, Liviu, et al.
Veröffentlicht: (2026)

Gromov's Approximating Tree and the All-Pairs Bottleneck Paths Problem
von: Cornect, Anders, et al.
Veröffentlicht: (2024)

Complexity of approximate conflict-free, linearly-ordered, and nonmonochromatic hypergraph colourings
von: Nakajima, Tamio-Vesa, et al.
Veröffentlicht: (2025)

Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability
von: Roberson, David E., et al.
Veröffentlicht: (2023)

Arithmetic Circuits and Neural Networks for Regular Matroids
von: Hertrich, Christoph, et al.
Veröffentlicht: (2025)

Neural Networks and (Virtual) Extended Formulations
von: Hertrich, Christoph, et al.
Veröffentlicht: (2024)

1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise
von: Ciardo, Lorenzo, et al.
Veröffentlicht: (2023)

Efficient approximation schemes for scheduling on a stochastic number of machines
von: Epstein, Leah, et al.
Veröffentlicht: (2024)

A Θ(m^9) ternary minimum-cost network flow LP model of the Assignment Problem polytope with applications to hard combinatorial optimization problems
von: Diaby, Moustapha
Veröffentlicht: (2016)

Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa
von: Bedert, Benjamin, et al.
Veröffentlicht: (2025)

On the Computational Complexity of Multi-Objective Ordinal Unconstrained Combinatorial Optimization
von: Figueira, José Rui, et al.
Veröffentlicht: (2024)

Optimal Inapproximability of Promise Equations over Finite Groups
von: Butti, Silvia, et al.
Veröffentlicht: (2024)

Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations
von: Focke, Jacob, et al.
Veröffentlicht: (2021)

Sparse Approximation in Lattices and Semigroups
von: Kuhlmann, Stefan, et al.
Veröffentlicht: (2024)

A Dichotomy for Maximum PCSPs on Graphs
von: Nakajima, Tamio-Vesa, et al.
Veröffentlicht: (2024)

Optimal b-Colourings and Fall Colourings in $H$-Free Graphs
von: Ahn, Jungho, et al.
Veröffentlicht: (2026)

Approximate cycle double cover
von: Ghanbari, Babak, et al.
Veröffentlicht: (2025)

A Classification of Long-Refinement Graphs for Colour Refinement
von: Kiefer, Sandra, et al.
Veröffentlicht: (2025)

On Rank-Monotone Graph Operations and Minimal Obstruction Graphs for the Lovász--Schrijver SDP Hierarchy
von: Au, Yu Hin, et al.
Veröffentlicht: (2024)

Colouring Graphs Without a Subdivided H-Graph: A Full Complexity Classification
von: Eagling-Vose, Tala, et al.
Veröffentlicht: (2025)

A Strongly Polynomial-Time Algorithm for Weighted General Factors with Three Feasible Degrees
von: Shao, Shuai, et al.
Veröffentlicht: (2023)

The Rise of Plurimorphisms: Algebraic Approach to Approximation
von: Barto, Libor, et al.
Veröffentlicht: (2024)

Reconfiguring Graph Homomorphisms on the Sphere
von: Lee, Jae-Baek, et al.
Veröffentlicht: (2018)

Determining the Outerthickness of Graphs Is NP-Hard
von: Lee, Pin-Hsian, et al.
Veröffentlicht: (2026)

Graph Irregularity via Edge Deletions
von: Bensmail, Julien, et al.
Veröffentlicht: (2025)

The Interplay Between Domination and Separation in Graphs
von: Chakraborty, Dipayan, et al.
Veröffentlicht: (2026)

Complexity Aspects of Homomorphisms of Ordered Graphs
von: Čertík, Michal, et al.
Veröffentlicht: (2025)

On Computational Aspects of Cores of Ordered Graphs
von: Čertík, Michal, et al.
Veröffentlicht: (2025)

Testing Isomorphism of Graphs in Polynomial Time
von: Xue, Rui
Veröffentlicht: (2023)

Finding d-Cuts in Claw-free Graphs
von: Ahn, Jungho, et al.
Veröffentlicht: (2025)

Local Homophily on Bicolored Graphs is $\mathbf{P}$-complete
von: Concha-Vega, Pablo
Veröffentlicht: (2026)

Finding Minimum Matching Cuts in $H$-free Graphs
von: Lucke, Felicia, et al.
Veröffentlicht: (2025)

Matching Cut and Variants on Bipartite Graphs of Bounded Radius and Diameter
von: Lucke, Felicia
Veröffentlicht: (2025)

Algorithmic methods of finite discrete structures. Graph clique problem
von: Kurapov, Sergey, et al.
Veröffentlicht: (2024)

Stable Set Polytopes with Rank $|V(G)|/3$ for the Lovász--Schrijver SDP Operator
von: Au, Yu Hin, et al.
Veröffentlicht: (2025)

On the complexity of symmetric vs. functional PCSPs
von: Nakajima, Tamio-Vesa, et al.
Veröffentlicht: (2022)

Maximum $k$- vs. $\ell$-colourings of graphs
von: Nakajima, Tamio-Vesa, et al.
Veröffentlicht: (2023)