Buchumschlag

Deterministic approximate counting of colorings with fewer than $2Δ$ colors via absence of zeros

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bencs, Ferenc, Berrekkal, Khallil, Regts, Guus
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Combinatorics Discrete Mathematics Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Improved bounds on the zeros of the chromatic polynomial of graphs and claw-free graphs
von: Bencs, Ferenc, et al.
Veröffentlicht: (2025)

Barvinok's interpolation method meets Weitz's correlation decay approach
von: Bencs, Ferenc, et al.
Veröffentlicht: (2025)

Near optimal bounds for weak and strong spatial mixing for the anti-ferromagnetic Potts model on trees
von: Bencs, Ferenc, et al.
Veröffentlicht: (2023)

Approximating the volume of a truncated relaxation of the independence polytope
von: Bencs, Ferenc, et al.
Veröffentlicht: (2024)

Improved bounds for the zeros of the chromatic polynomial via Whitney's Broken Circuit Theorem
von: Jenssen, Matthew, et al.
Veröffentlicht: (2023)

A near-optimal zero-free disk for the Ising model
von: Patel, Viresh, et al.
Veröffentlicht: (2023)

On zeros and algorithms for disordered systems: mean-field spin glasses
von: Bencs, Ferenc, et al.
Veröffentlicht: (2025)

A linear-time algorithm for $(1+ε)Δ$-edge-coloring
von: Bernshteyn, Anton, et al.
Veröffentlicht: (2024)

Deterministic approximation for the volume of the truncated fractional matching polytope
von: Guo, Heng, et al.
Veröffentlicht: (2024)

Approximating maximum-size properly colored forests
von: Bai, Yuhang, et al.
Veröffentlicht: (2024)

Improved bounds for coloring locally sparse hypergraphs
von: Iliopoulos, Fotis
Veröffentlicht: (2020)

Maximum list $r$-colorable induced subgraphs in $kP_3$-free graphs
von: Galby, Esther, et al.
Veröffentlicht: (2025)

On the complex zeros and the computational complexity of approximating the reliability polynomial
von: Bencs, Ferenc, et al.
Veröffentlicht: (2025)

Totally $Δ$-modular IPs with two non-zeros in most rows
von: Kober, Stefan
Veröffentlicht: (2024)

Strong spatial mixing for colorings on trees and its algorithmic applications
von: Chen, Zongchen, et al.
Veröffentlicht: (2023)

A Faster Deterministic Algorithm for Mader's $\mathcal{S}$-Path Packing
von: Iwata, Satoru, et al.
Veröffentlicht: (2024)

On boundedness of zeros of the independence polynomial of tori
von: de Boer, David, et al.
Veröffentlicht: (2023)

A logarithmic approximation of linearly ordered colourings
von: Håstad, Johan, et al.
Veröffentlicht: (2024)

Integrating High-Dimensional Functions Deterministically
von: Gamarnik, David, et al.
Veröffentlicht: (2024)

Edge coloring of products of signed graphs
von: Janczewski, Robert, et al.
Veröffentlicht: (2023)

Deterministic counting from coupling independence
von: Chen, Xiaoyu, et al.
Veröffentlicht: (2024)

Thin Trees via $k$-Respecting Cut Identities
von: Daga, Mohit
Veröffentlicht: (2025)

Traversing combinatorial 0/1-polytopes via optimization
von: Merino, Arturo, et al.
Veröffentlicht: (2023)

Generalising the maximum independent set algorithm via Boolean networks
von: Gadouleau, Maximilien, et al.
Veröffentlicht: (2024)

Dvorak-Dell-Grohe-Rattan theorem via an asymptotic argument
von: Kozachinskiy, Alexander
Veröffentlicht: (2025)

Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth
von: Korhonen, Tuukka, et al.
Veröffentlicht: (2024)

Improved Space-Time Tradeoffs for Permutation Problems via Extremal Combinatorics
von: Ameli, Afrouz Jabal, et al.
Veröffentlicht: (2026)

Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification
von: Jeronimo, Fernando Granha, et al.
Veröffentlicht: (2022)

Problems on Group-labeled Matroid Bases
von: Hörsch, Florian, et al.
Veröffentlicht: (2024)

$α_i$-Metric Graphs: Hyperbolicity
von: Dragan, Feodor F., et al.
Veröffentlicht: (2024)

Rainbow Arborescence Conjecture
von: Bérczi, Kristóf, et al.
Veröffentlicht: (2024)

Exact and Heuristic Computation of the Scanwidth of Directed Acyclic Graphs
von: Holtgrefe, Niels, et al.
Veröffentlicht: (2024)

Cuts in Graphs with Matroid Constraints
von: Banik, Aritra, et al.
Veröffentlicht: (2024)

Robust Contraction Decomposition for Minor-Free Graphs and its Applications
von: Bandyapadhyay, Sayan, et al.
Veröffentlicht: (2024)

Randomized Greedy Online Edge Coloring Succeeds for Dense and Randomly-Ordered Graphs
von: Dudeja, Aditi, et al.
Veröffentlicht: (2024)

Clique-free t-matchings in degree-bounded graphs
von: Paluch, Katarzyna, et al.
Veröffentlicht: (2024)

On the sizes of BDDs and ZDDs representing matroids
von: Emoto, Hiromi, et al.
Veröffentlicht: (2024)

On the number of $k$-mers admitting a given lexicographical minimizer
von: Ingels, Florian, et al.
Veröffentlicht: (2024)

Sparsest cut and eigenvalue multiplicities on low degree Abelian Cayley graphs
von: d'Orsi, Tommaso, et al.
Veröffentlicht: (2024)

On the enumeration of signatures of XOR-CNF's
von: Creignou, Nadia, et al.
Veröffentlicht: (2024)