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.

Háromszögkeresési probléma
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(m1,41) időben megoldható. Egy másik megközelítés A3 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(n2,373)-ra viszi le, ahol n a csúcsok számát jelöli.

Ahogy  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, Θ(n2). Kvantumalgoritmusok esetén a legjobb ismert alsó korlát Ω(n), de a legjobb ismert algoritmus csak O(n35/27).

Függetlenségi szám és Ramsey-elmélet
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). Ez a korlát kissé élesíthető: bármely háromszögmentes gráfban létezik  csúcsból álló független halmaz és egyes háromszögmentes gráfokban minden független halmaz  csúcsból áll. 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ó, 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  függetlenségi számú gráfot eredményez. Hasonló tulajdonságú reguláris gráfok is előállíthatók.

Ezek az eredmények értelmezhetők úgy is, hogy  alakú aszimptotikus korlátokat adnak az R(3,t) Ramsey-számokra: ha egy  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.

Háromszögmentes gráfok színezése

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ő. 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  á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.  és  megmutatták, hogy egy m-élű háromszögmentes gráf színezéséhez szükséges színek száma:

é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.  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  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ő;  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.  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  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 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.

Kapcsolódó szócikkek
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

Jegyzetek 

Források

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

Fordítás

További információk 
 

Gráfcsaládok
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 legfeljebbklikkszámú gráfok , a legalábbgirthparaméterű gráfok , a feszített részgráfkéntkö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 . Háromszögkeresési probléma 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( m1,41 ) időben megoldható . Egy másik megközelítés A3 nyomának keresése , ahol A a gráf szomszédsági mátrixa . A nyom pontosan akkor 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( n2,373)-ra viszi le , ahol n a csúcsok számát jelöli . Ahogy 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 , Θ( n2 ) . Kvantumalgoritmusok esetén a legjobb ismert alsó korlát Ω ( n ) , de a legjobb ismert algoritmus csak O( n35/27 ) . Függetlenségi szám és Ramsey-elmélet 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 ) . Ez a korlát kissé élesíthető : bármely háromszögmentes gráfban létezik csúcsból álló független halmaz és egyes háromszögmentes gráfokban minden független halmaz csúcsból áll . 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ó , 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 függetlenségi számú gráfot eredményez . Hasonló tulajdonságú reguláris gráfok is előállíthatók . Ezek az eredmények értelmezhetők úgy is , hogy alakú aszimptotikus korlátokat adnak az R( 3,t ) Ramsey-számokra : ha egy 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 . Háromszögmentes gráfok színezése 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 ( mindenszínezhető gráf ) háromszögmentes , és a Grötzsch-tétel kimondja , hogy minden háromszögmentes síkgráfszínezhető . 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 á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 kapottcsú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. és megmutatták , hogy egy m-élű háromszögmentes gráf színezéséhez szükséges színek száma : é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. bizonyította , hogy egy n-csúcsú háromszögmentes gráf , amiben minden csúcs fokszáma meghaladja a/5-öt , biztosan páros gráf . Ez a legjobb lehetséges ilyen jellegű eredmény , hiszen azcsúcsból álló kör színezéséhez három színre van szükség és minden csúcsnak pontosan/5 szomszédja van . Ebből az eredményből kiindulva 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ő ; 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. megmutatta , hogy bármely n-csúcsú háromszögmentes gráf , amiben a csúcsok fokszáma nagyobb/29-nél,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/29 a fokszáma . Végül 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 talált példát tetszőlegesen nagy kromatikus számú és minimális fokszámú –3 − ε)n bármely ε > 0-ra – háromszögmentes gráfra . Kapcsolódó szócikkek 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 Jegyzetek Források . . . . . . . . . . . . . . . . . . . . . . . . . Fordítás További információk Gráfcsaládok