Háromszögmentes gráf

A matematika, azon belül a gráfelmélet területén egy háromszögmentes gráf olyan irányítatlan gráf, melyben semelyik három csúcs élei nem alkotnak háromszöget. A háromszögmentes gráfok úgy is definiálhatók, mint a legfeljebb 2 klikkszámú gráfok, a legalább 4 girthparaméterű gráfok, a feszített részgráfként 3-kör nélküli gráfok, illetve a lokálisan független gráfok (melyekben tetszőleges csúcs nyílt szomszédsága független).

A Turán-tétel alapján az n-csúcsú háromszögmentes gráfok közül a maximális élszámú a teljes páros gráf, melyben a két partíció elemszáma a lehető legközelebb van egymáshoz.

A háromszögkeresési probléma célja annak eldöntése, hogy egy gráf háromszögmentes-e vagy sem. Ha a gráf tartalmaz háromszöget, az algoritmustól gyakran elvárják, hogy kimenetében megadjon a gráfban háromszöget alkotó három csúcsot.

Egy m éllel rendelkező gráf tesztelése O(m^1,41) időben megoldható.^[1] Egy másik megközelítés A³ nyomának keresése, ahol A a gráf szomszédsági mátrixa. A nyom pontosan akkor 0, ha a gráf háromszögmentes. Sűrű gráfok esetében hatékony lehet ezt az egyszerű, mátrixszorzáson alapuló algoritmust használni, mivel a feladat bonyolultságát O(n^2,373)-ra viszi le, ahol n a csúcsok számát jelöli.

Ahogy (Imrich, Klavžar & Mulder 1999) kimutatta, a háromszögmentes gráfok felismerése ekvivalens bonyolultságú a mediángráfok felismerésével; jelenleg azonban az ismert legjobb mediángráf-kereső algoritmusok használják szubrutinként a háromszögkeresést, és nem fordítva.

A probléma döntésifa-komplexitása vagy kérdéskomplexitása, ahol a kérdések a gráf szomszédsági mátrixát tároló jósnak szólnak, Θ(n²). Kvantumalgoritmusok esetén a legjobb ismert alsó korlát Ω(n), de a legjobb ismert algoritmus csak O(n^35/27).^[2]

Egy n-csúcsú háromszögmentes gráfban könnyen található √n csúcsból álló független halmaz: két eset lehetséges, az elsőben létezik olyan csúcs, aminek √n-nél több szomszédja van (ekkor szomszédai független csúcshalmazt alkotnak) a másodikban az összes csúcsnak √n-nél kevesebb szomszédja van (ekkor bármely maximális független csúcshalmaz legalább √n csúcsból áll).^[3] Ez a korlát kissé élesíthető: bármely háromszögmentes gráfban létezik ${\displaystyle \Omega ({\sqrt {n\log n}})}$ csúcsból álló független halmaz és egyes háromszögmentes gráfokban minden független halmaz ${\displaystyle O({\sqrt {n\log n}})}$ csúcsból áll.^[4] Az olyan háromszögmentes gráfok generálására, melyekben minden független halmaz kisméretű, a háromszögmentes eljárás (triangle-free process) alkalmazható,^[5] melyben véletlenszerű, háromszöget nem adó éleket adunk hozzá egy gráfhoz, így próbálván elérni a maximális háromszögmentes gráfot. Ez a folyamat nagy valószínűséggel ${\displaystyle O({\sqrt {n\log n}})}$ függetlenségi számú gráfot eredményez. Hasonló tulajdonságú reguláris gráfok is előállíthatók.^[6]

Ezek az eredmények értelmezhetők úgy is, hogy ${\displaystyle \Theta ({\tfrac {t^{2}}{\log t}})}$ alakú aszimptotikus korlátokat adnak az R(3,t) Ramsey-számokra: ha egy ${\displaystyle \Omega ({\tfrac {t^{2}}{\log t}})}$ csúcsú teljes gráfot pirosra és kékre színezünk akkor vagy a piros gráf tartalmaz egy háromszöget, vagy ha a piros gráf háromszögmentes, akkor kell legyen egy t méretű független csúcshalmaza, ami a kék gráf azonos méretű klikkjének felel meg.

A háromszögmentes gráfok kutatásának jelentős részét teszi ki a gráfszínezés vizsgálata. Minden páros gráf (minden 2-színezhető gráf) háromszögmentes, és a Grötzsch-tétel kimondja, hogy minden háromszögmentes síkgráf 3-színezhető.^[7] A síkba nem rajzolható háromszögmentes gráfok színezéséhez azonban sokkal több színre is szükség lehet.

A (Mycielski 1955) által megalkotott konstrukció (Mycielski-konstrukció), ami egy háromszögmentes gráfból egy nagyobb, egyben nagyobb kromatikus számú gráfot állít elő. Ha egy gráf kromatikus száma k, a Mycielski-konstrukció k + 1 kromatikus számú gráfot állít elő, így ez a konstrukció felhasználható annak megmutatására, hogy egy síkba nem rajzolható háromszögmentes gráf színezéséhez tetszőlegesen sok színre lehet szükség. Jellegzetes példa a Mycielski-konstrukció ismételt alkalmazásával kapott 11 csúcsú Grötzsch-gráf, aminek színezéséhez legalább négy színre van szükség; ez a legkisebb ilyen tulajdonsággal rendelkező gráf.^[8] (Gimbel & Thomassen 2000) és (Nilli 2000) megmutatták, hogy egy m-élű háromszögmentes gráf színezéséhez szükséges színek száma:

${\displaystyle O\left({\frac {m^{1/3}}{(\log m)^{2/3}}}\right)}$

és hogy valóban léteznek háromszögmentes gráfok, melyek kromatikus száma ezzel a korláttal arányos.

Számos eredmény létezik a háromszögmentes gráfok színezései és fokszámuk összefüggésében. (Andrásfai, Erdős & Sós 1974) bizonyította, hogy egy n-csúcsú háromszögmentes gráf, amiben minden csúcs fokszáma meghaladja a 2n/5-öt, biztosan páros gráf. Ez a legjobb lehetséges ilyen jellegű eredmény, hiszen az 5 csúcsból álló kör színezéséhez három színre van szükség és minden csúcsnak pontosan 2n/5 szomszédja van. Ebből az eredményből kiindulva (Erdős & Simonovits 1973) azt a sejtést állították fel, mely szerint bármely n-csúcsú háromszögmentes gráfot, amiben a csúcsok fokszáma legalább n/3, három színnel kiszínezhető; (Häggkvist 1981) azonban cáfolta a sejtést egy ellenpéldával, amiben a Grötzsch-gráf minden csúcsát egy jól megválasztott méretű független csúcshalmazzal cserélte ki. (Jin 1995) megmutatta, hogy bármely n-csúcsú háromszögmentes gráf, amiben a csúcsok fokszáma nagyobb 10n/29-nél, 3-színezhető; ez a legjobb elérhető eredmény, mivel a Häggkvist által adott ellenpélda négy színt igényel és pontosan 10n/29 a fokszáma. Végül (Brandt & Thomassé 2006) igazolta, hogy bármely n-csúcsú háromszögmentes gráf, amiben a csúcsok fokszáma nagyobb n/3-nál, négy színnel kiszínezhető. További ilyen jellegű eredmények nem várhatók, mivel Hajnal^[9] talált példát tetszőlegesen nagy kromatikus számú és minimális fokszámú – (1/3 − ε)n bármely ε > 0-ra – háromszögmentes gráfra.

• Henson-gráf, egy végtelen háromszögmentes gráf, ami feszített részgráfként tartalmazza az összes véges háromszögmentes gráfot
• Egyszínű háromszög probléma, adott gráf éleinek két háromszögmentes gráfba való particionálása

Források

• Ez a szócikk részben vagy egészben a Triangle-free graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

• Graphclass: triangle-free, <http://www.graphclasses.org/classes/gc_371.html>