A matematika, azon belül a gráfelmélet területén a Colin de Verdière-gráfinvariáns vagy Colin de Verdière-invariáns – jelölése tetszőleges G gráfra – Yves Colin de Verdière által 1990-ben bevezetett gráfparaméter. Meghatározásának motivációja egyes Schrödinger-operátorok második sajátértékei maximális multiplicitásának vizsgálata volt.
Definíció Legyen egy hurokmentes egyszerű gráf. Az általánosság megszorítása nélkül tegyük fel, hogy . Ekkor bármely szimmetrikus mátrix legnagyobb ko-rangja (egy -es mátrix ko-rangja , ahol a mátrix rangja), melyre: bármely -re, ahol : ha és ha ; M-nek pontosan egyetlen negatív sajátértéke van, melynek multiplicitása 1; nem létezik olyan nemnulla mátrix, melyre , illetve olyan, melyre ha akár , akár igaz.
Ismert gráfcsaládok karakterizációi Néhány jól ismert gráfcsalád karakterizálható Colin de Verdière-invariánsuk szerint: pontosan akkor áll fenn, ha G nem rendelkezik élekkel;. pontosan akkor áll fenn, ha G lineáris erdő (utak diszjunkt uniója); nem írja ezt explicit módon, de az általa használt jellemzésből – háromszög és mancs minor nélküli gráfok – pontosan ez vezethető le. pontosan akkor áll fenn, ha G külsíkgráf; pontosan akkor áll fenn, ha G síkbarajzolható;. pontosan akkor áll fenn, ha G láncmentesen beágyazható..
Ugyanezek a gráfcsaládok megjelennek a gráf Colin de Verdière-invariánsa és komplementer gráfjának szerkezete kapcsolatában: Ha egy n-csúcsú gráf komplementere lineáris erdő, akkor ;. Ha egy n-csúcsú gráf komplementere külsíkgráf, akkor ; Ha egy n-csúcsú gráf komplementere síkbarajzolható, akkor .
Gráfminorok Egy gráf minora az eredeti gráfból élek összehúzásával, élek és csúcsok törlésével kapott gráf. A Colin de Verdière-invariáns minor-monoton, ami azt jelenti, hogy a minorképzés műveletével a gráf invariánsát csak csökkenteni vagy változatlanul hagyni lehet: Ha H minora G-nek, akkor . A Robertson–Seymour-tétel értelmében minden k-hoz létezik gráfok H véges halmaza, melyre igaz, hogy a legfeljebb k invariánsú gráfok megegyeznek a minorként H egyik tagját sem tartalmazó gráfokkal. listázza ezeket a tiltott minorokat k ≤ 3-ra; k = 4-re a tiltott minorok halmaza a Petersen-gráfcsalád hét gráfjából áll, a csomómentesen beágyazható gráfok két karakterizációja alapján, miszerint a gráfok, melyekre μ ≤ 4 és melyeknek nincs Petersen-családbeli minoruk.
Kromatikus szám sejtése szerint egy μ Colin de Verdière-invariánsú gráf színezhető legfeljebb μ + 1 színnel. Például a lineáris erdők invariánsa 1, és 2-színezhetők; a külsíkgráfok invariánsa kettő, és 3-színezhetők, és a síkbarajzolható gráfok (a négyszíntétel értelmében) 4-színezhetők.
A legfeljebb 4-es Colin de Verdière-invariánsú gráfokra a sejtés igaz; az, hogy a csomómentesen beágyazható gráfok kromatikus száma legfeljebb öt, következménye a Hadwiger-sejtés K6-minormentes gráfokra való bizonyításának, amit végzett el.
Egyéb tulajdonságok Ha egy gráf metszési száma , akkor Colin de Verdière-invariánsa legfeljebb . Például a két Kuratowski-féle gráfot, a öt és a -at le lehet rajzolni egyetlen metszéssel, Colin de Verdière-invariánsuk ezért legfeljebb négy.
Boxicitással való kapcsolata Ugyanazon gráf Colin de Verdière-invariánsa és boxicitása között Louis Esperet a következő összefüggést igazolta: , továbbá valószínűsíti, hogy a boxicitás legfeljebb a Colin de Verdière-invariánssal egyenlő.
Befolyás A Colin de Verdière-invariánst a gráfhoz tartozó speciális mátrixosztály alapján definiálják, nem csak egyetlen, a gráfhoz tartozó mátrixból. Hasonló módon definiáltak néhány más gráfparamétert is, mint például a gráf minimális rangját, a gráf minimális szemidefinit rangját és a gráf minimális ferde rangját.
Fordítás
Jegyzetek
. Translated by Neil Calkin as . .
. .
Kategória:Gráfinvariánsok Kategória:Gráfminorok