On Minimal Transversals of Maximal Cliques in Graphs
<|reference_start|>On Minimal Transversals of Maximal Cliques in Graphs: A hypergraph is conformal if it is the family of maximal cliques of a graph. In this paper we are interested in the problem of determining when is the family of minimal transversal of maximal cliques of a graph conformal. Such graphs are called clique dually conformal (CDC for short). As our main results, we completely characterize CDC graphs within the families of triangle-free graphs and split graphs. Both characterizations lead to polynomial-time recognition algorithms. We also show that the class of CDC graphs is closed under substitution, in the strong sense that substituting a graph $H$ for a vertex of a graph $G$ results in a CDC graph if and only if both $G$ and $H$ are CDC.<|reference_end|>
@article{boros2024on,
    title={On Minimal Transversals of Maximal Cliques in Graphs},
    author={Endre Boros, Vladimir Gurvich, Martin Milaniv{c}, Dmitry Tikhanovsky,
  Yushi Uno},
    journal={arXiv preprint arXiv:2405.10789},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.10789},
    primaryClass={math.CO cs.DM cs.DS}
}