Biklikkmentes gráf

A matematika, azon belül a gráfelmélet területén egy gráf akkor t-biklikk-mentes (biclique-free), t-páros klikkmentes vagy t-teljes páros gráf-mentes, ha nem tartalmazza a 2t-csúcsú, tehát a K_t,t teljes páros gráfot részgráfjaként. Egy gráfcsalád akkor biklikkmentes, ha létezik olyan t szám, amire a család összes gráfja t-biklikkmentes. A biklikkmentes gráfok a ritka gráfok családjának egyik legáltalánosabb tagjai. Fellépnek diszkrét geometriai illeszkedési problémák kapcsán és parametrizált komplexitású problémákban is előkerülnek.

Tulajdonságok

Ritkaság

A Kővári–Sós–Turán-tétel szerint az n-csúcsú t-biklikkmentes gráfok éleinek nagyságrendje O(n^{2 − 1/t}), ami jóval kevesebb egy sűrű gráf éleinél. Megfordítva, ha egy gráfcsaládot tiltott részgráfjai alapján határozunk meg, illetve a részgráfképzés műveletére nézve zárt és nem tartalmaz tetszőlegesen nagyméretű sűrű gráfokat, akkor szükségképpen t-biklikkmentes valamely t értékre, különben nagy, sűrű teljes páros gráfokat kellene tartalmaznia.

Alsó korlátként (Erdős, Hajnal & Moon 1964) sejtése szerint minden maximális t-biklikkmentes páros gráf (maximális olyan értelemben, hogy nem adható hozzá további él anélkül, hogy t-biklikk jönne létre) legalább (t − 1)(n + m − t + 1) élt tartalmaz, ahol n és m a bipartíció két oldalának csúcsszámai.

Kapcsolat más ritkagráf-családokkal

Egy d degeneráltságú gráf szükségképpen (d + 1)-biklikkmentes. Ráadásul a sehol sem sűrű gráfok osztálya biklikkmentes. Általánosabban, ha létezik n-csúcsú gráf, ami a gráfcsalád egyetlen tagjának sem 1 mélységű korlátos mélységű minorja, akkor a család n-biklikkmentes, hiszen az összes n-csúcsú gráf a K_n,n 1 mélységű sekély minorja. Ily módon a biklikkmentes gráfcsaládok a ritka gráfok két, legáltalánosabb osztályát egyesítik.

Alkalmazások

Diszkrét geometria

A diszkrét geometria területén fellépő illeszkedési gráfok számos fajtája biklikkmentes. Erre egyszerű példa, hogy az euklideszi síkon véges számú pont és egyenes illeszkedési gráfja sohasem tartalmazza a K_2,2 részgráfot.

Parametrizált komplexitás

A parametrizált komplexitás területén a biklikkmentes gráfok olyan algoritmusokban bukkannak fel, melyek hatékonyan kezelnek megfelelően kicsi bemeneti értékekkel rendelkező ritka gráfokat. Konkrétan a t-biklikkmentes gráfokban a k méretű domináló csúcshalmaz keresése rögzített paraméter mellett kezelhető, ha a paraméter k + t, még akkor is, ha meggyőző bizonyítékok mutatnak arra, hogy ez nem lehetséges, ha kizárólag k a paraméter. Hasonló eredményeket igazoltak a domináló halmaz-probléma több változatára. Ugyanezzel a paraméterezéssel tesztelhető az is, hogy valamely, legfeljebb k méretű domináló halmaz átvihető-e egy másikba csúcsok hozzáadásának és törlésének láncolatán keresztül, miközben a domináló tulajdonság megmarad.