The complexity of recognizing ABAB-free hypergraphs

DOI10.46298/DMTCS.14610MaRDI QIDQ6987001zbMATH OpenFDO

Authors Gábor Damásdi, Balázs Keszegh, Dömötör Pálvölgyi, Karamjeet Singh

Publication date 7 May 2025

Published in Discrete Mathematics and Theoretical Computer Science. DMTCS (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.46298/DMTCS.14610

zbMATH Keywords

complexityhypergraphsNP-hardness

Mathematics Subject Classification ID

Hypergraphs (05C65) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites work

• An abstract approach to polychromatic coloring: shallow hitting sets in ABA-free hypergraphs and pseudohalfplanes
• Coloring hypergraphs defined by stabbed pseudo-disks and ABAB-free hypergraphs
• Helly-type theorems for the ordering of the vertices of a hypergraph
• Incidence matrices and interval graphs
• On the chromatic number of general Kneser hypergraphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Total Ordering Problem

This page was built for publication: The complexity of recognizing \(ABAB\)-free hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6987001)