V teorii grafů je t - beaclick - free graf graf, ve kterém nejsou žádné úplné bipartitní grafy s 2 t vrcholy Kt , t jako podgrafy . Rodina grafů je prostá biklique, pokud existuje takové číslo t , že všechny grafy v rodině jsou prosté t -biklique. Rodiny bezcyklových grafů tvoří jeden z nejobecnějších typů rodin řídkých grafů . Vznikají při incidenčních problémech v kombinatorické geometrii a používají se také v parametrické teorii složitosti .
Podle Kovariho-Cos-Turanova teorému má každý t -bezcyklový graf s n vrcholy O ( n 2 − 1/ t ) hran, tzn. graf je mnohem vzácnější než hustý graf [1] . Naopak, je-li rodina grafů definována zakázanými podgrafy nebo je uzavřena pod přebíráním podgrafů a neobsahuje husté grafy libovolně velké velikosti, musí být prostá t -bicliques po určité t , jinak musí rodina obsahovat libovolně velké husté grafy. kompletní grafy.bipartitní grafy.
Jako spodní hranici Erdős, Hajnal a Muun [2] předpokládali, že každý maximální bipartitní graf bez t -biciliky (ke kterému nelze přidat hranu bez vytvoření t -biclique) má alespoň ( t − 1)( n + m − t + 1) hrany, kde n a m jsou počty vrcholů na každé z částí grafu [3] .
Graf s degenerací d je nutně bez ( d + 1) -bicliques. Navíc rodina grafů bez dvojkliků nesmí být nikde hustá, což znamená, že pro jakékoli číslo k existuje graf, který není k - mělký moll od žádného grafu v rodině. Konkrétně, existuje-li n -vrcholový graf, který není 1-mělký minor, pak rodina nesmí obsahovat n -bicliques, protože všechny grafy s n vrcholy jsou 1-mělkými menšími grafy K n , n . Rodiny grafů bez biclique tedy sjednocují dvě nejobecnější třídy řídkých grafů [4] .
V kombinatorické geometrii je známo , že mnoho typů incidenčních grafů neobsahuje bi-kliky. Jako jednoduchý příklad lze uvést, že graf incidence konečné množiny bodů a přímek na euklidovské rovině rozhodně neobsahuje podgraf K 2,2 [5] .
Grafy bez biclique se používají v parametrické teorii složitosti k vývoji algoritmů, které jsou účinné pro řídké grafy s dostatečně malými vstupními parametry. Zejména nalezení dominující množiny velikosti k na t -biclick-free grafech je problém řešitelný s pevnými parametry pomocí parametru k + t , i když existují dobré důvody, že to není možné pouze pomocí parametru k bez t . Stejné výsledky platí pro mnoho variant problému dominující množiny [4] . Kontrolu, zda má dominující množina velikost nejvýše k , lze také transformovat na další kontrolu se stejnou parametrizací řetězením vkládání a mazání vrcholů se zachováním vlastnosti dominance [6] .