Cover Image

Lower Bounds for the Pfaffian Number of Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Junchaya, Enrique, Miranda, Alberto Alexandre Assis, Lucchesi, Cláudio L.
Format:	Preprint
Published:	2026
Subjects:	Combinatorics Discrete Mathematics 05C85 (Primary), 05C70, 68R10 (Secondary) G.2.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

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

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

On the Number of Vertices/Edges whose Deletion Preserves the Konig-Egervary Property
by: Levit, Vadim E., et al.
Published: (2024)

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

Almost Bipartite non-König-Egerváry Graphs Revisited
by: Levit, Vadim E., et al.
Published: (2024)

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

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

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

A greedy heuristic for graph burning
by: García-Díaz, Jesús, et al.
Published: (2024)

On corona of Konig-Egervary graphs
by: Levit, Vadim E., et al.
Published: (2024)

Solving the Graph Burning Problem for Large Graphs
by: Pereira, Felipe de Carvalho, et al.
Published: (2024)

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

A note on the structure of locally finite planar quasi-transitive graphs
by: Giocanti, Ugo
Published: (2024)

Low Recourse Arborescence Forests Under Uniformly Random Arcs
by: Dahlmeier, J Niklas, et al.
Published: (2025)

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

Approximating branchwidth on parametric extensions of planarity
by: Thilikos, Dimitrios M., et al.
Published: (2023)

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

Open Packing in Graphs: Bounds and Complexity
by: Shalu, M. A., et al.
Published: (2024)

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)

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

The family of all local maximum independent sets is an augmentoid
by: Levit, Vadim E., et al.
Published: (2026)

Killing a Vortex
by: Thilikos, Dimitrios M., et al.
Published: (2022)

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

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

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)

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)

Tree-independence number VI. Thetas and pyramids
by: Chudnovsky, Maria, et al.
Published: (2025)

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

Algorithmic releases on the spanning trees of suitable graphs
by: Imbesi, Maurizio, et al.
Published: (2017)

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

Independent Set Enumeration and Estimation of Related Constants of Grid Graphs and Their Variants
by: Liang, Kai
Published: (2025)

Exponential Lower Bounds for the Pfaffian Number of Graphs
by: Pant, Priyanshu, et al.
Published: (2026)

Exact Algorithms for MaxCut on Split Graphs
by: Lalovic, Marko
Published: (2024)

On the Relation Between Treewidth, Tree-Independence Number, and Tree-Chromatic Number of Graphs
by: Koutsoutis, Alex, et al.
Published: (2025)

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