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).

Az adott csúcsszámhoz tartozó legnagyobb élszámú háromszögmentes gráfok a kiegyensúlyozott teljes páros gráfok.

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(m^1,41) időben megoldható.Sablon:Sfnp 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 Sablon:Harvtxt 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).

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 $\mathrm{\Omega }(\sqrt{n\log n})$ csúcsból álló független halmaz és egyes háromszögmentes gráfokban minden független halmaz $O(\sqrt{n\log n})$ csúcsból áll.Sablon:Sfnp 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 $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.Sablon:Sfnp

Ezek az eredmények értelmezhetők úgy is, hogy $\mathrm{\Theta }(\frac{t^2}{\log t})$ alakú aszimptotikus korlátokat adnak az R(3,t) Ramsey-számokra: ha egy $\mathrm{\Omega }(\frac{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.

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

A Grötzsch-gráf olyan háromszögmentes gráf, amit nem lehet négynél kevesebb színnel kiszínezni

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

$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. Sablon:Harvtxt 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 Sablon:Harvtxt 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ő; Sablon:Harvtxt 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. Sablon:Harvtxt 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 Sablon:Harvtxt 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

• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.

Fordítás

• Sablon:Fordítás

További információk

• Sablon:Citation