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)., ami a korábbi által megadott algoritmus javítása.

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). p. 184, Avi Wigderson egy korábbi színezés-approximációs algoritmusának ötlete alapján 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 HajnalLásd . 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

Kategória:Gráfcsaládok