A gráfelméletben a t - beaclick - mentes gráf olyan gráf, amelyben nincsenek teljes kétrészes gráfok , amelyekben 2 t csúcsú K t , t részgráfok szerepelnének. Egy gráfcsalád mentes a biklikektől, ha létezik olyan t szám , amelyre a család minden gráfja mentes a t -biclikektől. A kerékpármentes gráfcsaládok a ritka gráfcsaládok egyik legáltalánosabb típusát alkotják . Felmerülnek a kombinatorikus geometriában előfordulási problémákban, és a parametrikus komplexitáselméletben is használják .
A Kovari-Cos-Turan tétel szerint minden n csúcsú t -bicikli nélküli gráfnak O ( n 2 − 1/ t ) éle van, azaz. a gráf sokkal ritkább, mint a sűrű gráf [1] . Ezzel szemben, ha egy gráfcsaládot tiltott részgráfok határoznak meg, vagy részgráfok felvétele zárva van, és nem tartalmaz tetszőlegesen nagy méretű sűrű gráfokat, akkor bizonyos t esetén mentesnek kell lennie a t -biclikkektől , ellenkező esetben a családnak tetszőlegesen nagy sűrűségű gráfokat kell tartalmaznia. teljes gráfok, kétrészes gráfok.
Alsó korlátként Erdős, Hajnal és Muun [2] azt sejtették, hogy minden maximális t -biclikk nélküli bipartit gráfnak (amelyhez nem adható él a t -biclikk létrehozása nélkül) legalább ( t − 1)( n + m − t + 1) élek, ahol n és m a csúcsok száma a gráf egyes részein [3] .
A d degenerációjú gráf szükségszerűen mentes a ( d + 1) -bikliktől. Ezenkívül a biklik nélküli gráfok családja sehol sem lehet sűrű, ami azt jelenti, hogy bármely k számhoz létezik olyan gráf, amely nem a család egyik gráfjának k - sekély minorja . Konkrétan, ha létezik olyan n csúcsú gráf, amely nem 1-es sekély moll, akkor a családnak n -bikliktől mentesnek kell lennie, mivel minden n csúcsú gráf a K n , n gráf 1-sekély molljai . Így a biklik nélküli gráfcsaládok a ritka gráfok két legáltalánosabb osztályát egyesítik [4] .
A kombinatorikus geometriában sokféle előfordulási gráfról ismert, hogy mentes a bi-klikkektől. Egyszerű példaként elmondható, hogy az euklideszi síkon egy véges pont- és egyeneshalmaz beesési gráfja biztosan nem tartalmaz K 2,2 részgráfot [5] .
A Biclique-mentes gráfokat a parametrikus komplexitáselméletben használják olyan algoritmusok kifejlesztésére, amelyek hatékonyak ritka gráfokhoz, kellően kis bemeneti paraméterekkel. Konkrétan egy domináns k méretű halmaz megtalálása t -bikattintásmentes gráfokon fix paraméterekkel megoldható probléma a k + t paraméter használatával , még akkor is, ha jó okai vannak annak, hogy ez nem lehetséges csak a k paraméter használatával t nélkül . Ugyanezek az eredmények igazak a domináns halmazprobléma számos változatára [4] . Annak ellenőrzése, hogy a domináns halmaz legfeljebb k méretű- e, a csúcsok beszúrásának és törlésének láncolásával egy másik, azonos paraméterezésű ellenőrzéssé is átalakítható, megőrizve a dominancia tulajdonságot [6] .