Klikový graf neorientovaného grafu G je dalším grafem K ( G ), který představuje klikovou strukturu grafu G.
O klikových grafech se diskutuje minimálně od roku 1968 [1] a popis klikových grafů byl uveden v roce 1971 [2] .
Klika grafu G je množina X vrcholů grafu G , která má tu vlastnost, že jakákoliv dvojice odlišných vrcholů X je spojena hranou v G . Maximální klika G je klika X vrcholů G tak, že neexistuje žádná klika vrcholu Y z G , která by obsahovala všechny vrcholy X plus alespoň jeden další vrchol.
Je -li dán graf G , jeho klikový graf K ( G ) je graf takový, že
Graf H je klikovým grafem K ( G ) jiného grafu právě tehdy, když v H existuje množina C klik, jejíž množina pokrývá všechny hrany H tak, že C tvoří rodinu Hellyů . To znamená, že pokud je S podmnožinou C s tou vlastností, že libovolné dva prvky S mají neprázdný průsečík, pak S sám musí mít neprázdný průsečík. Kliky v množině C však nemusí být maximální kliky [2] .
Jestliže H = K ( G ), lze zkonstruovat rodinu C tohoto typu, ve které každá klika v C odpovídá vrcholu v v G a skládá se z klik grafu G obsahujících v . Všechny tyto kliky mají ve svém průsečíku v , takže tvoří kliku v H . Takto konstruovaná rodina C má vlastnost Helly, protože každá podrodina C s neprázdným párovým průnikem musí odpovídat klikě v G , kterou lze rozšířit na maximální kliku, která patří do průniku podrodiny [2] .
Naopak, pokud H má klikovou rodinu Helly C pokrývající všechny hrany H , pak je to klikový graf K ( G ) pro G , jehož vrcholy jsou disjunktním spojením vrcholů H a prvků C . Tento graf G má hranu pro každou dvojici klik v C s neprázdným průsečíkem a pro každou dvojici vrcholů v H a kliku v C , která ji obsahuje. Tento graf však neobsahuje žádné hrany spojující dvojice vrcholů v H . Maximální kliky v tomto grafu G se skládají z jednoho vrcholu grafu H , přičemž všechny kliky z C jej obsahují a jejich graf průsečíku je izomorfní s grafem H [2] .
Tento popis však nevede k efektivním algoritmům - problém rozpoznání, zda je daný graf klikovým grafem, je NP-úplný [4] .