Cover Image

The classification of minimally unsatisfiable 2-CNFs -- a fundamental study

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Abbasizanjani, Hoda, Kullmann, Oliver
Format:	Preprint
Published:	2020
Subjects:	Discrete Mathematics Combinatorics 05C60, 05C90, 03B05, 68R99 F.2.2; G.2.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Bounds on the Twin-Width of Product Graphs
by: Pettersson, William, et al.
Published: (2022)

Census Dual Graphs: Properties and Random Graph Models
by: Anderson, Sara, et al.
Published: (2026)

Independent Set Enumeration in King Graphs by Tensor Network Contractions
by: Liang, Kai
Published: (2025)

Completely independent spanning trees in the hypercube
by: Shaw, Benedict Randall
Published: (2024)

Excluding a Ladder as an Induced Minor in Graphs Without Induced Stars
by: Choi, Mujin, et al.
Published: (2025)

A Fast 3-Approximation for the Capacitated Tree Cover Problem with Edge Loads
by: Rockel-Wolff, Benjamin
Published: (2024)

A new density limit for unanimity in majority dynamics on random graphs
by: Kim, Jeong Han, et al.
Published: (2025)

On the complexity of Sandwich Problems for $M$-partitions
by: Barsukov, Alexey, et al.
Published: (2026)

Quickly excluding an annotated planar graph
by: Gorsky, Maximilian, et al.
Published: (2026)

The price of homogeneity is polynomial
by: Gorsky, Maximilian, et al.
Published: (2026)

Three iterations of $(d-1)$-WL test distinguish non isometric clouds of $d$-dimensional points
by: Rose, Valentino Delle, et al.
Published: (2023)

Metrics on Permutation Families Defined by a Restriction Graph
by: Tymoshenko, Danylo, et al.
Published: (2025)

The frequency $K_i$s for symmetrical traveling salesman problem
by: Wang, Yong
Published: (2025)

Temporalizing digraphs via linear-size balanced bi-trees
by: Bessy, Stéphane, et al.
Published: (2023)

Counting Kernels in Directed Graphs with Arbitrary Orientations
by: Jartoux, Bruno
Published: (2022)

Computing the forcing spectrum of outerplanar graphs in polynomial time
by: Gorsky, Maximilian, et al.
Published: (2024)

Catching Rats in $H$-minor-free Graphs
by: Gorsky, Maximilian, et al.
Published: (2025)

On Strict Brambles
by: Lardas, Emmanouil, et al.
Published: (2022)

W-state graphs: Structure and Algorithms
by: Gajjala, Rishikesh, et al.
Published: (2026)

Thick Forests
by: Dyer, Martin, et al.
Published: (2023)

Some Thoughts on Graph Similarity
by: Grohe, Martin
Published: (2024)

A Systematic Approach to Crossing Numbers of Cartesian Products with Paths
by: Asiri, Zayed, et al.
Published: (2024)

How Local Separators Shape Community Structure in Large Networks
by: Frenkel, Sarah, et al.
Published: (2025)

Optimal Bounds for the k-Disjoint Paths Problem
by: Cavallaro, Dario, et al.
Published: (2026)

The Directed Disjoint Paths Problem with Congestion
by: Bentert, Matthias, et al.
Published: (2025)

Exploration of $k$-edge-deficient temporal graphs in linear time
by: Lahtin, Ivan, et al.
Published: (2026)

On λ-backbone coloring of cliques with tree backbones in linear time
by: Michalik, Krzysztof, et al.
Published: (2021)

Homomorphism Counts to Trees
by: Dawar, Anuj
Published: (2024)

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

Local iterative algorithms for approximate symmetry guided by network centralities
by: Hartman, David, et al.
Published: (2025)

Monotonically Decreasing the Number of Directed 3-Cycles via Edge-Flips?
by: Bom, David, et al.
Published: (2025)

Graphs whose vertices of degree at least 2 lie in a triangle
by: Forte, Vinicius L. do, et al.
Published: (2022)

Simple Approximations for General Spanner Problems
by: Bökler, Fritz, et al.
Published: (2025)

Exact Minimum Weight Spanners via Column Generation
by: Bökler, Fritz, et al.
Published: (2024)

Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics
by: Chimani, Markus, et al.
Published: (2021)

Compact Representation of Semilinear and Terrain-like Graphs
by: Cardinal, Jean, et al.
Published: (2025)

Delineating Half-Integrality of the Erdős-Pósa Property for Minors: the Case of Surfaces
by: Paul, Christophe, et al.
Published: (2024)

The Local Structure Theorem for Graph Minors with finite index
by: Paul, Christophe, et al.
Published: (2025)

Polynomial Bounds for the Graph Minor Structure Theorem
by: Gorsky, Maximilian, et al.
Published: (2025)

Lower Bounds for the Pfaffian Number of Graphs
by: Junchaya, Enrique, et al.
Published: (2026)