Leírás
Legyen D egy kxn-es pozitív egész mátrix, amelyben minden sor összege 2n-2, azaz minden sora egy fának a fokszámsorozata. A kérdés az, hogy mikor van D-nek élfüggetlen hernyó realizációja, azaz mikor van k olyan éldiszjunkt hernyó, amelyben a j-edik hernyó fokai épp a j-edik sor. Megadjuk a szükséges és elégséges feltételt k = 2-re. Azt sejtjük, hogy tetszőleges k-ra egy elégséges feltétel az, ha minden oszlopban legfeljebb egy 1-es érték van. Ezt a sejtést bizonyítjuk k = 3-ra. Ez a sejtés egy erősebb változata egy korábbi sejtésünknek, amely szerint a megadott tulajdonságú fokszámmátrixnak mindig van élfüggetlen fa realizációja. A sejtés bizonyításához azt kellene bizonyítani, hogy megfelelő méretű éldiszjunkt monokromatikus utakban mindig van olyan maximális méretű tarka párosítás, amely elkerül egy előírt tiltott pontot. Közös munka Zhangyang Wei BSM-es diákkal.m