20.500.12556/RUP-22211 Conformality of minimal transversals of maximal cliques Given a hypergraph ℋ, the dual hypergraph of ℋis the hypergraph of all minimal transversals of ℋ. A hypergraph is conformal if it is the family of maximal cliques of a graph. In a recent work, Boros, Gurvich, Milanič, and Uno (Journal of Graph Theory, 2025) studied conformality of dual hypergraphs and proved several results related to this property, leading in particular to a polynomial-time algorithm for recognizing graphs in which, for any fixed k, all minimal transversals of maximal cliques have size at most k. In this follow-up work, we provide a novel aspect to the study of graph clique transversals, by considering the dual conformality property from the perspective of graphs. More precisely, we study graphs for which the family of minimal transversals of maximal cliques is conformal. Such graphs are called clique dually conformal (CDC for short). It turns out that the class of CDC graphs is a rich generalization of the class of P4-free graphs. As our main results, we completely completely characterize CDC graphs within the families of triangle-free graphs and split graphs. Both characterizations lead to polynomial-time recognition algorithms. Generalizing the fact that every P4-free graph is CDC, 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. maximal clique minimal transversal conformal hypergraph triangle-free graph split graph maksimalna klika minimalna transverzala konformen hipergraf graf brez trikotnikov razcepljen graf true false true Angleški jezik Slovenski jezik Članek v reviji 2025-12-16 15:13:27 2025-12-16 15:13:29 2025-12-19 03:05:53 0000-00-00 00:00:00 2026 0 0 str. 1-25 iss. 1, [article no.] 114657 Vol. 349 Jan. 2026 0000-00-00 Zaloznikova NiDoloceno NiDoloceno 0000-00-00 0000-00-00 2025-07-09 519.17 0012-365X 10.1016/j.disc.2025.114657 261722883 RAZ_Boros_Endre_2026.pdf RAZ_Boros_Endre_2026.pdf 1 04AF3790F99DB379FC60E308C53240CF 072f5fc34c2248ceb317a29057cc113b5d842d4197fe69b5857c3715e4a7d6fa df26a9ca-da89-11f0-8f0b-005056ac49c0 https://repozitorij.upr.si/Dokument.php?lang=slv&id=32245 https://www.sciencedirect.com/science/article/pii/S0012365X25002651?via%3Dihub 1 b30b9bb1-da89-11f0-8f0b-005056ac49c0 https://repozitorij.upr.si/Dokument.php?lang=slv&id=32244 Fakulteta za matematiko, naravoslovje in informacijske tehnologije Inštitut Andrej Marušič 0 0 0