Háromszögmentes gráf

A Wikipédiából, a szabad enciklopédiából

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öggrá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ög-keresési probléma[szerkesztés]

A háromszög-keresé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ó.[1] 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 (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, Θ(n2). Kvantumalgoritmusok esetén a legjobb ismert alsó korlát Ω(n), de legjobb ismert algoritmus csak O(n35/27).[2]

Függetlenségi szám és Ramsey-elmélet[szerkesztés]

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 csúcsból álló független halmaz és egyes háromszögmentes gráfokban minden független halmaz 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 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 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[szerkesztés]

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ő.[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:

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

Kapcsolódó szócikkek[szerkesztés]

Jegyzetek[szerkesztés]

  1. Alon, Yuster & Zwick (1994).
  2. (Lee, Magniez & Santha 2013), ami a korábbi (Belovs 2012) által megadott algoritmus javítása.
  3. (Boppana & Halldórsson 1992) p. 184, Avi Wigderson egy korábbi színezés-approximációs algoritmusának ötlete alapján
  4. Kim (1995).
  5. (Erdős, Suen & Winkler 1995); (Bohman 2009).
  6. Alon, Ben-Shimon & Krivelevich (2010).
  7. (Grötzsch 1959); (Thomassen 1994)).
  8. Chvátal (1974).
  9. Lásd (Erdős & Simonovits 1973).
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>.

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 has order of magnitude ", 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[szerkeszté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.

További információk[szerkesztés]

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