Problem dodeljevanja frekvenc išče ustrezno dodelitev frekvenc oddajnikom v brezžičnem omrežju in obsega množico specifičnih podproblemov. Poseben primer je problem pakirnega barvanja grafov, ki izhaja iz regulacije dodeljevanja frekvenc radijskim postajam. Problem je opisan s pomočjo teorije grafov kot pakirno kromatično število $\chi_{\rho}(G)$ grafa $G$. Pakirno kromatično število grafa $G$ je najmanjše tako celo število $k$, da obstaja razbitje množice vozlišč $V(G)$ v disjunktne razrede $X_1, . . . , X_k$ s pogojem, da imajo vozlišča v $X_i$ medsebojno razdaljo večjo kot $i$. Problem določitve pakirnega kromatičnega števila je znan kot NP-težek. Članek predstavlja uporabo modela celoštevilskega linearnega programiranja ter modela problema izpolnjivosti za izračun pakirnega kromatičnega števila. Modela sta uporabljena za študij pakirnega kromatičnega števila kartezičnih produktov poti in ciklov ter razdaljnih grafov.
COBISS.SI-ID: 21043464
Pakirno kromatično število $\chi_{\rho}(G)$ grafa $G$ je najmanjše celo število $k$, tako da lahko množico vozlišč grafa $G$ razdelimo v množice $\Pi_1,\ldots,\Pi_k$, kjer je $\Pi_i$ ($i \in [k]$) $i$-pakiranje. Postavljena in raziskovana je naslednja domneva: če je $G$ podkubičen graf, potem je $\chi_{\rho}(S(G))\le 5$, kjer je $S(G)$ subdivizija grafa $G$. Domneva je dokazana za vse posplošene prizme ciklov. Da dokažemo ta rezultat, je tudi dokazano, da če je $G$ posplošena prizma cikla, potem je$G$ $(1,1,2,2)$-obarvljiv natanko tedaj, ko $G$ ni Petersenov graf. Veljavnost domneve je nadalje dokazana za grafe, ki jih lahko dobimo iz posplošenih prizm tako, da enega izmed dveh $n$-ciklov nadomestimo z unijo ciklov, med katerimi je največ en 5-cikel. Obravnavano je tudi pakirno kromatično število grafov dobljenih s subdivizijo vsake izmed njegovih povezan enakokrat.
COBISS.SI-ID: 17889113
V članku podamo pozitiven odgovor na vprašanje M. O. Albertsona [M.O. Albertson, You can't paint yourself into a corner, J. Combin. Theory Ser. B 73(2) (1998) 189-194], ali vsak ravninski graf premore 5-seznamsko-barvanje tudi v primeru, ko vsebuje predbarvana vozlišča, če so le dovolj daleč drugo od drugega.
COBISS.SI-ID: 17882713
Znano je, da obstajata le dva minimalna neravninska grafa: $K_5$ in $K_{3,3}$ (vozlišča stopnje 2 so nepomembna v tem kontekstu). V jeziku prekrižnih števil sta ta dva grafa edina 1-prekrižno-kritična grafa: vsak ima prekrižno število najmanj ena in vsak pravi podgraf ima prekrižno število manj kot ena. Leta 1987 je Kochol konstruiral neskončno družino 3-povezanih, enostavnih, 2-prekrižno-kritičnih grafov. V tem delu: (i) določimo vse 3-povezane 2-prekrižno-kritične grafe, ki vsebujejo subdivizijo Möbiusove lestve $V_{10}$; (ii) pokažemo, kako dobiti vse grafe, ki niso 3-povezani, a so 2-prekrižno-kritični, iz tistih grafov, ki so 3-povezani; (iii) pokažemo, da obstaja samo končno mnogo 3-povezanih 2-prekrižno-kritičnih grafov, ki ne vsebujejo subdivizije $V_{10}$; in (iv) določimo vse 3-povezane 2-križno-kritične grafe, ki ne vsebujejo subdivizije $V_8$.
COBISS.SI-ID: 17611353
V članku obravnavamo končne, povezavno-tranzitivne direktne in krepke produtke ter tudi neskončne šibke kartezične produkte. Dokazano je, da je direktni produkt dveh povezanih, nedvodelnih grafov povezavno-tranzitiven natanko tedaj, ko sta oba faktorja povezavno-tranzitivna in je vsaj en faktor ločno-tranzitiven, ali pa je en faktor povezavno-tranzitiven in je drugi faktor polni graf z zankami v vseh vozliščih. Dokazano je tudi, da je krepki produkt povezavno-tranzitiven natanko tedaj, ko so vsi faktorji polni grafi. Nadalje je dokazano, da je povezan, neskončni kartezični produktni graf $G$ povezavno-tranzitiven natanko tedaj, ko je vozliščno-tranzitiven in je $G$ končna šibka kartezična potenca povezanega, povezavno- in vozliščno-tranzitivnega grafa $H$, ali pa je $G$ šibka kartezična potenca povezanega, dvodelnega, povezavno-tranzitivnega grafa $H$, ki ni vozliščno-tranzitiven.
COBISS.SI-ID: 17670745