Conformal hypergraphs: duality and implications for the upper clique transversal problem

DOI10.1002/JGT.23238MaRDI QIDQ6962794zbMATH OpenFDO

Authors Endre Boros, Vladimir Gurvich, Martin Milanič, Yushi Uno

Publication date 8 July 2025

Published in Journal of Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1002/JGT.23238

zbMATH Keywords

conformal hypergraphdual hypergraphhypergraphmaximal cliqueupper clique transversal

Mathematics Subject Classification ID

Computational methods for problems pertaining to combinatorics (05-08) Hypergraphs (05C65) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• A characterization of claw-free CIS graphs and new results on the order of CIS graphs
• A global parallel algorithm for the hypergraph transversal problem
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A New Algorithm for Generating All the Maximal Independent Sets
• A note on the size of minimal covers
• Algorithm Theory - SWAT 2004
• Algorithmic aspects of clique-transversal and clique-independent sets
• Algorithmic Aspects of Neighborhood Numbers
• Algorithmic graph theory and perfect graphs
• An improved upper bound on maximal clique listing via rectangular fast matrix multiplication
• Anti-blocking polyhedra
• Approximation algorithms for clique transversals on some graph classes
• Blockers and antiblockers of stable matchings
• Blocking and anti-blocking pairs of polyhedra
• Blocking and Antiblocking Polyhedra
• Bottleneck extrema
• Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
• Clique-perfectness of complements of line graphs
• Clique-transversal sets and clique-coloring in planar graphs
• Clique-transversal sets of line graphs and complements of line graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Complete-subgraph-transversal-sets problem on bounded treewidth graphs
• Computing and Combinatorics
• Covering the cliques of a graph with vertices
• Cut-threshold graphs
• Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
• Distance-hereditary graphs are clique-perfect
• Dual subimplicants of positive Boolean functions
• Ein Satz über Untermengen einer endlichen Menge.
• Generalizations of Grillet's theorem on maximal stable sets and maximal cliques in graphs
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• scientific article; zbMATH DE number 5852793 (Why is no real title available?)
• scientific article; zbMATH DE number 3845624 (Why is no real title available?)
• scientific article; zbMATH DE number 3825713 (Why is no real title available?)
• scientific article; zbMATH DE number 3906537 (Why is no real title available?)
• scientific article; zbMATH DE number 3974960 (Why is no real title available?)
• scientific article; zbMATH DE number 3657692 (Why is no real title available?)
• scientific article; zbMATH DE number 3691392 (Why is no real title available?)
• scientific article; zbMATH DE number 43754 (Why is no real title available?)
• scientific article; zbMATH DE number 3606472 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1016362 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• scientific article; zbMATH DE number 3400923 (Why is no real title available?)
• HYPERGRAPHS
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• Imperfect and nonideal clutters: A common approach
• Lexicographically maximal edges of dual hypergraphs and Nash-solvability of tight game forms
• Linear separation of connected dominating sets in graphs
• Logical Aspects of Combinatorial Duality
• On covering all cliques of a chordal graph
• On exact blockers and anti-blockers, \(\varDelta \)-conjecture, and related problems
• On graphs whose maximal cliques and stable sets intersect
• On k-trestles in polyhedreal graphs
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• On the Desirability of Acyclic Database Schemes
• On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs
• Optimal‐size clique transversals in chordal graphs
• Random graphs.
• Reducibility among combinatorial problems
• Sublinear-space and bounded-delay algorithms for maximal clique enumeration in graphs
• The edge covering number of the intersection of two matroids
• The Erdős-Hajnal conjecture. A survey
• The Grötzsch theorem for the hypergraph of maximal cliques
• Total domishold graphs: a generalization of threshold graphs, with connections to threshold hypergraphs
• Transformations on regular nondominated coteries and their applications
• Upper Clique Transversals in Graphs

Cited in

(1)

• Conformality of minimal transversals of maximal cliques

This page was built for publication: Conformal hypergraphs: duality and implications for the upper clique transversal problem

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