Leírás
A gráfszínezések egy jól ismert terület a gráfelméletben. Eredetileg
interaktív protokollon keresztül értelmezett kvantum analogonja a
kvantumkromatikus szám - a cikk ezt a témát járja körbe.
Jelenleg nem ismert algoritmus ami nemtriviális kvantumszínezést adna egy
gráfhoz - a legtöbb ismert algoritmus a gráf d-dimenziós ortogonális
reprezentációján alapul. Ez igen limitált hozzáállás, mivel a gráf
ortogonális rangja és a kvantum kromatikus szám között nem feltétlenül van
kapcsolat, erre példákat is fogunk látni.
Egy nemrég felfedezett példa demonstrál majd ehhez hasonló jelenségeket:
például ha a gráfhoz egy új csúcsot adunk, amit minden korábbival
összekötünk, akkor nem biztos, hogy nő a kvantum-kromatikus száma a
gráfnak, továbbá ez a gráf a legkisebb tanú, hogy a kvantum és a klasszikus
kromatikus szám nem mindig egyenlő.