Wykres bez trójkąta

W teorii wykres , A wykres bez trójkąta jest wykresem, który nie posiada triplet krawędzi tworzących trójkąt.

Własność matematyczna

Teoria Ramseya

Twierdzenie Mantela, szczególny przypadek twierdzenia Turána , to:

Maksymalna liczba krawędzi na wykresie bez trójkąta to $\ lfloor n ^ {2} / 4 \ rfloor.$

Właściwości jako rodzina

Rodzina grafów bez trójkąta zawiera w szczególności grafy acykliczne i jest zawarta w grafach bez rombów .

Uznanie

Wykresy bez trójkątów można rozpoznać w czasie , gdzie jest liczba krawędzi. $O (m ^ {{1,41}})$ $m$

Mówiąc bardziej ogólnie, możemy rozpoznać grafy, które nie mają cykli o określonej długości (ustalonej w algorytmie), w czasie (z liczbą wierzchołków) lub w czasie . $O (nm)$ $nie$ $O (n ^ {\ omega} \ log (n))$

Problem jest również badany w dziedzinie testowania własności .

Kolorowanie

Grötzsch twierdzenie wynika, że każdy płaski wykres bez trójkąta ma-3 zabarwienia, jak definicje barwienia wykresu .

Najmniejszy wykres bez trójkąta z liczbą chromatyczną większą lub równą 4 to wykres Grötzscha (ilustracja) .

Uwagi i odniesienia

Dokładniej en , gdzie jest wykładnik mnożenia macierzy , patrz ( Alon, Yuster i Zwick 1994 ) oraz ( Alon, Yuster i Zwick 1997 ) $O (m ^ {2 \ omega / (\ omega +1)})$ $\omega$
(w) Burkhard Monien , „ How to find path along Efficiently ” , North-Holland Mathematics Studies , vol. 109,1985, s. 239-254 ( czytaj online )
(w) N. Alon , R. Yuster i U. Zwick , „ Kodowanie kolorami ” , Journal of the ACM , t. 42, n o 4,1995, s. 844-856 ( czytaj online )
Noga Alon , Tali Kaufman, Michael Krivelevich i Dana Ron, „ Testing Triangle-Freeness in General Graphs ”, SIAM J. Discrete Math. , vol. 22 N O 2 2008, s. 786-819 ( DOI 10.1137 / 07067917X )

Bibliografia

(en) Noga Alon , R. Yuster i U. Zwick , „Finding and counting specified length cycle ” , w: Proceedings of the 2nd European Symposium on Algorithms , Utrecht, Holandia ,1994, s. 354-364.
(en) N. Alon , R. Yuster i U. Zwick , „ Finding and counting specified length cycle ” , Algorithmica ,1997, s. 354-364 ( czytaj online ).
(de) Herbert Grötzsch , „ 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 , tom. 8,1959, s. 109 - 120.

Linki zewnętrzne

Wykresy bez trójkąta w systemie informacyjnym o klasach grafów i ich włączeniach .