A matematika, azon belül a gráfelmélet területén egy gráf akkor -biklikk-mentes (biclique-free), t-páros klikkmentes vagy -teljes páros gráf-mentes, ha nem tartalmazza a 2-csúcsú, tehát a teljes páros gráfot részgráfjaként. Egy gráfcsalád akkor biklikkmentes, ha létezik olyan szám, amire a család összes gráfja -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 -csúcsú -biklikkmentes gráfok éleinek nagyságrendje , ami jóval kevesebb egy sűrű gráf éleinél.. Kővári Tamás, T. Sós Vera és Turán Pál munkája a biklikk-mentes páros gráfok élszámával foglalkozik, de a valószínűségi módszer standard alkalmazásával ugyanezt a korlátot tetszőleges gráfokra is el lehet érni. 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 -biklikkmentes valamely értékre, különben nagy, sűrű teljes páros gráfokat kellene tartalmaznia.
Alsó korlátként sejtése szerint minden maximális -biklikkmentes páros gráf (maximális olyan értelemben, hogy nem adható hozzá további él anélkül, hogy -biklikk jönne létre) legalább élt tartalmaz, ahol és a bipartíció két oldalának csúcsszámai..
Kapcsolat más ritkagráf-családokkal Egy degeneráltságú gráf szükségképpen -biklikkmentes. Ráadásul a sehol sem sűrű gráfok osztálya biklikkmentes. Általánosabban, ha létezik -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 -biklikkmentes, hiszen az összes -csúcsú gráf a 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 részgráfot.. Lásd a Lemma 3.1-et és az azt követő megjegyzéseket.
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 -biklikkmentes gráfokban a méretű domináló csúcshalmaz keresése rögzített paraméter mellett kezelhető, ha a paraméter , még akkor is, ha meggyőző bizonyítékok mutatnak arra, hogy ez nem lehetséges, ha kizárólag 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 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. .
Jegyzetek
Kategória:Extremális gráfelmélet Kategória:Gráfcsaládok