Korsningar i kompletta multipartita grafer

Sammanfattning

Syftet med den här uppsatsen är att undersöka graden av planäritet för

kompletta multipartita grafer. Det primära resultatet som presenteras är en

formel som kan användas för att nedåt begränsa det minsta antalet korsningar

som behövs för att realisera en komplett bipartit graf indelad i m

respektive n noder: cr(K_{m,,n}) >= q - 2p + 4, m >= n >= 2, där q = mn och

p = m + n. Därutöver presenteras tabeller som med formeln som utgångspunkt

uppskattar eller bestämmer det minsta antalet korsningar för alla

kompletta multipartita grafer med sju noder eller mindre.

Uppsatsen innehåller också en genomgång av några tidigare resultat, däribland

Zarankiewicz uppställning av kompletta bipartita grafer samt en överblick

över Crossing Number Inequality