Zsúfolt gróf

A túltelített gráf [ 1] egy egyszerű gráf (több él és hurok nélkül), amelynek mérete nagyobb, mint a csúcsai maximális fokának és a sorrendjének a felének a szorzata lefelé kerekítve . $G$ $|E|$ $\displaystyle \Delta (G)$ $|V|$

|E|>\Delta (G)\lfloor |V|/2\rfloor

Ha egy gráfnak túlteljes részgráfja van, és = akkor - , azt részgráf-túlteljes gráfnak nevezzük [ 2] [ 3] . $G$ $S$ $\displaystyle \Delta (S)$ $\displaystyle \Delta (G)$ $G$

A túlcsordulási gráf fogalmát a gráf éleinek színezési problémáinak mérlegelésekor vezették be, nevezetesen annak eldöntésekor, hogy egy gráf az 1. vagy a 2. osztályba tartozik-e. Amint a Vizing tételből következik, a gráf kromatikus indexe lehet , és akkor a gráf az 1. osztályba tartozik, vagy és akkor a gráf a 2. osztályba tartozik. $\chi ^{\prime }(G)=\Delta (G)$ $\chi ^{\prime }(G)=\Delta (G)+1$

Tulajdonságok

A túlcsordulási grafikonok néhány tulajdonsága:

Az [1] tételből , amely szerint ha egy gráf mérete akkora , hogy hol a függetlenségi él száma és csúcsainak maximális foka, akkor a gráf a 2. osztályba tartozik, és a feltételek, hogy ha a gráf sorrendű , akkor annak függetlenségi élszáma , a tulajdonság a következő: $G$ $|E|$ $|E|>\beta _{1}(G)\Delta (G)$ $\beta _{1}(G)$ $\Delta (G)$ $G$ $|V|$ $\beta _{1}(G)=\lfloor |V|/2\rfloor$

A zsúfolt grafikon egy 2. osztályú gráf

Tételként bizonyítjuk [2] :

Ha egy gráfnak van túlcsordulási részgráfja, akkor maga a gráf túlcsordult.

Tételként bizonyítjuk [1] .

A zsúfolt gráf sorrendje páratlan szám

Túlcsordulási sejtés

Chetwind és Hilton [4] 1986- ban javasolta az úgynevezett Overfull Graph sejtést .

Ha egy gráf csúcsainak maximális foka teljesíti a feltételt , ahol a gráf sorrendje, akkor a gráf akkor és csak akkor tartozik a 2. osztályba, ha túlcsordulási részgráfos gráfról van szó.

3\Delta (G)\geqslant |V|

|V|

G

Ennek a sejtésnek, ha igaz, számos alkalmazása lenne a gráfelméletben, beleértve az 1-faktorizációs sejtést [5] .

Algoritmusok

A [6] -ban egy algoritmus található, amely lehetővé teszi egy olyan gráf megtalálását , amelyhez az összes generált túlcsordulási részgráf időben , ahol és . $G$ $|V(S)|>|V(G)|-\Delta (G)$ $S$ $O(n\log(n)+m)$ $n=|V(G)|$ $m=|E(G)|$

Ennek az algoritmusnak egy változata lehetővé teszi egy gráf számára , hogy megtalálja az összes generált túlcsordulási részgráfot lineáris időben . $G$ $2\Delta (G)\geq |V(G)|$ $O(n+m)$

A cikk bemutatja a második algoritmust is, amely az első algoritmussal működik, amely lehetővé teszi, hogy megtalálja a gráf összes generált túlcsordulási részgráfját , amely általános esetben polinomiális időben , egy szabályos gráf esetén pedig időben . $G$ $3\Delta (G)\geq |V(G)|$ $O(n^{5/3}m)$ $G$ $O(n^{3})$

Jegyzetek

↑ 1 2 3 Chartran, 2009 , p. 258.
↑ 12 Chartran , 2009 , p. 260.
↑ Hilton, 1989 .
↑ Chetwynd, Hilton, 1986 , p. 303–317.
↑ Chetwynd, Hilton, 1989 , p. 103–112.
↑ Niessen, 2001 .

Irodalom

Chartran G., Zhang P. Kromatikus gráfelmélet (angol) / sorozatszerkesztő Kenneth H. Rosen. - Baca Ration, London, New York: Chapman & Hall/CRC, 2009. - P. 483. - (Diszkrét matematika és alkalmazásai). - ISBN 978-1-58488-800-0 .

Chetwynd AG, Hilton AJW Csillagok multigráfjai három maximális fokozattal // Mathematical Proceedings of the Cambridge Philosophical Society. - 1986. - 1. évf. 100 , iss. 2 . — P. 303–317 . - doi : 10.1017/S030500410006610X .
Chetwynd AG, Hilton AJW 1 magas fokú szabályos gráfok faktorizálása – továbbfejlesztett korlát // Matematika . - 1989. - 1. évf. 75 , iss. 1–3 . — P. 103–112 . - doi : 10.1016/0012-365X(89)90082-4 .
Hilton AJW Két sejtés az élszínezésről // Diszkrét matematika. - 1989. - 1. évf. 74 . — P. 61-64 .
Niessen T. Hogyan találhatunk túlteljes részgráfokat nagy maximális fokszámú gráfokban. II (angol) // Electronic Journal of Combinatorics. - 2001. - 20. évf. 8 , iss. 1 . (7. kutatási cikk)