On exact blockers and anti-blockers, -conjecture, and related problems

DOI10.1016/J.DAM.2010.11.014MaRDI QIDQ628313zbMATH OpenOpenAlexWikidataFDO

Authors Vladimir Gurvich

Publication date 10 March 2011

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2010.11.014

zbMATH Keywords

blockerCIS graph\(\varDelta \)-conjectureanti-blockerbox-partitionCIS \(d\)-graphsexact anti-blockerexact blockerread-once Boolean functionsolid box-partition

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Recommendations

• Blocking and Antiblocking Polyhedra
• Algorithms – ESA 2004
• Deltas, extended odd holes and their blockers
• Blockers and transversals
• A note on blockers in posets

Cites work

• scientific article; zbMATH DE number 5852793 (Why is no real title available?)
• scientific article; zbMATH DE number 4145688 (Why is no real title available?)
• scientific article; zbMATH DE number 3494450 (Why is no real title available?)
• scientific article; zbMATH DE number 3545568 (Why is no real title available?)
• scientific article; zbMATH DE number 3338381 (Why is no real title available?)
• A characterization of almost CIS graphs
• A note on perfect graphs
• An improvement on the complexity of factoring read-once Boolean functions
• Colored graphs without colorful cycles
• Combinatorial characterization of read-once formulae
• Decomposing complete edge-chromatic graphs and hypergraphs. Revisited
• Edge colorings of complete graphs without tricolored triangles
• Edge-colored complete graphs with precisely colored subgraphs
• Generalizations of Grillet's theorem on maximal stable sets and maximal cliques in graphs
• Graph pairs and their entropies: Modularity problems
• Imperfect and nonideal clutters: A common approach
• Lambda composition
• Not complementary connected and not CIS \(d\)-graphs form weakly monotone families
• On graphs whose maximal cliques and stable sets intersect
• On split and almost CIS-graphs
• Perfect couples of graphs
• Proof of Chvátal's conjecture on maximal stable sets and maximal cliques in graphs
• Transitiv orientierbare Graphen
• Vertex- and edge-minimal and locally minimal graphs

Cited in

(8)

• Sandwich problem for \(\varPi\)- and \(\varDelta\)-free multigraphs and its applications to positional games
• Characterizing (quasi-)ultrametric finite spaces in terms of (directed) graphs
• On equistable, split, CIS, and related classes of graphs
• On CIS circulants
• Detecting strong cliques
• Strong cliques in diamond-free graphs
• Block seriation problems: A unified approach. Reply to the problem of H. Garcia and J. M. Proth (Applied Stochastic Models and Data Analysis, 1, (1), 25–34 (1985))
• Strong cliques in vertex‐transitive graphs

Describes a project that uses

Uses Software

• JBool

This page was built for publication: On exact blockers and anti-blockers, \(\varDelta \)-conjecture, and related problems

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