| Naslov: | Conformality of minimal transversals of maximal cliques |
|---|
| Avtorji: | ID Boros, Endre (Avtor)
ID Gurvich, Vladimir (Avtor)
ID Milanič, Martin (Avtor)
ID Tikhanovsky, Dmitry (Avtor)
ID Uno, Yushi (Avtor) |
|---|
| Datoteke: |  RAZ_Boros_Endre_2026.pdf (1,65 MB)
MD5: 04AF3790F99DB379FC60E308C53240CF
 https://www.sciencedirect.com/science/article/pii/S0012365X25002651?via%3Dihub
|
|---|
| Jezik: | Angleški jezik |
|---|
| Vrsta gradiva: | Članek v reviji |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: | FAMNIT - Fakulteta za matematiko, naravoslovje in informacijske tehnologije
IAM - Inštitut Andrej Marušič
|
|---|
| Opis: | 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. |
|---|
| Ključne besede: | maximal clique, minimal transversal, conformal hypergraph, triangle-free graph, split graph |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Datum objave: | 09.07.2025 |
|---|
| Leto izida: | 2026 |
|---|
| Št. strani: | str. 1-25 |
|---|
| Številčenje: | Vol. 349, iss. 1, [article no.] 114657 |
|---|
| PID: | 20.500.12556/RUP-22211  |
|---|
| UDK: | 519.17 |
|---|
| ISSN pri članku: | 0012-365X |
|---|
| DOI: | 10.1016/j.disc.2025.114657 |
|---|
| COBISS.SI-ID: | 261722883 |
|---|
| Datum objave v RUP: | 16.12.2025 |
|---|
| Število ogledov: | 170 |
|---|
| Število prenosov: | 2 |
|---|
| Metapodatki: |    |
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Skupna ocena: | (0 glasov) |
|---|
| Vaša ocena: | Ocenjevanje je dovoljeno samo prijavljenim uporabnikom. |
|---|
| Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
