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

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 $\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. 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.

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

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 (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. (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:

$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 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

• Alon, Noga; Ben-Shimon, Sonny & Krivelevich, Michael (2010), "A note on regular Ramsey graphs", Journal of Graph Theory 64 (3): 244–249, DOI 10.1002/jgt.20453.
• Alon, N.; Yuster, R. & Zwick, U. (1994), "Finding and counting given length cycles", Proceedings of the 2nd European Symposium on Algorithms, Utrecht, The Netherlands, pp. 354–364.
• Andrásfai, B.; Erdős, P. & Sós, V. T. (1974), "On the connection between chromatic number, maximal clique and minimal degree of a graph", Discrete Mathematics 8 (3): 205–218, DOI 10.1016/0012-365X(74)90133-2.
• Belovs, Aleksandrs (2012), "Span programs for functions with constant-sized 1-certificates", Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing (STOC '12), New York, NY, USA: ACM, pp. 77–84, ISBN 978-1-4503-1245-5, DOI 10.1145/2213977.2213985.
• Biderman, Stella; Cuddy, Kevin & Li, Ang et al. (2015), On the Sensitivity of k-Uniform Hypergraph Properties.
• Bohman, Tom (2009), "The triangle-free process", Advances in Mathematics 221 (5): 1653–1677, DOI 10.1016/j.aim.2009.02.018.
• Boppana, Ravi & Halldórsson, Magnús M. (1992), "Approximating maximum independent sets by excluding subgraphs", BIT 32 (2): 180–196, DOI 10.1007/BF01994876.
• Brandt, S. & Thomassé, S. (2006), Dense triangle-free graphs are four-colorable: a solution to the Erdős-Simonovits problem, <http://perso.ens-lyon.fr/stephan.thomasse/liste/vega11.pdf>. Hozzáférés ideje: 2016-10-06.
• Chiba, N. & Nishizeki, T. (1985), "Arboricity and subgraph listing algorithms", SIAM Journal on Computing 14 (1): 210–223, DOI 10.1137/0214017.
• Chvátal, Vašek (1974), "The minimality of the Mycielski graph", Graphs and combinatorics (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973), vol. 406, Lecture Notes in Mathematics, Springer-Verlag, pp. 243–246.
• Erdős, P. & Simonovits, M. (1973), "On a valence problem in extremal graph theory", Discrete Mathematics 5 (4): 323–334, DOI 10.1016/0012-365X(73)90126-X.
• Erdős, P.; Suen, S. & Winkler, P. (1995), "On the size of a random maximal graph", Random Structures and Algorithms 6 (2–3): 309–318, DOI 10.1002/rsa.3240060217.
• Gimbel, John & Thomassen, Carsten (2000), "Coloring triangle-free graphs with fixed size", Discrete Mathematics 219 (1-3): 275–277, DOI 10.1016/S0012-365X(00)00087-X.
• Grötzsch, H. (1959), "Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel", Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Reihe 8: 109–120.
• Häggkvist, R. (1981), "Odd cycles of specified length in nonbipartite graphs", Graph Theory (Cambridge, 1981), pp. 89–99.
• Hatami, Pooya; Kulkarni, Raghav & Pankratov, Denis (2010), Variations on the Sensitivity Conjecture.
• Imrich, Wilfried; Klavžar, Sandi & Mulder, Henry Martyn (1999), "Median graphs and triangle-free graphs", SIAM Journal on Discrete Mathematics 12 (1): 111–118, DOI 10.1137/S0895480197323494.
• Itai, A. & Rodeh, M. (1978), "Finding a minimum circuit in a graph", SIAM Journal on Computing 7 (4): 413–423, DOI 10.1137/0207033.
• Jin, G. (1995), "Triangle-free four-chromatic graphs", Discrete Mathematics 145 (1-3): 151–170, DOI 10.1016/0012-365X(94)00063-O.
• Kim, J. H. (1995), "The Ramsey number $R(3,t)$ has order of magnitude ${\tfrac {t^{2}}{\log t}}$", Random Structures and Algorithms 7: 173–207, DOI 10.1002/rsa.3240070302.
• Lee, Troy; Magniez, Frédéric & Santha, Miklos (2013), "Improved quantum query algorithms for triangle finding and associativity testing", Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013), New Orleans, Louisiana, pp. 1486–1502, ISBN 978-1-611972-51-1.
• Mycielski, J. (1955), "Sur le coloriage des graphes", Colloq. Math. 3: 161–162.
• Nilli, A. (2000), "Triangle-free graphs with large chromatic numbers", Discrete Mathematics 211 (1–3): 261–262, DOI 10.1016/S0012-365X(99)00109-0.
• Shearer, J. B. (1983), "Note on the independence number of triangle-free graphs", Discrete Mathematics 46 (1): 83–87, DOI 10.1016/0012-365X(83)90273-X.
• Thomassen, C. (1994), "Grötzsch's 3-color theorem", Journal of Combinatorial Theory, Series B 62 (2): 268–279, DOI 10.1006/jctb.1994.1069.

Fordítás

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

További információk

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