ERK'2021, Portorož, 305-308 305 Radijsko k-barvanje neskončnih mrež Danilo Korže 1 , Aleksander Vesel 2 , 1 Univerza v Mariboru, Fakulteta za elektrotehniko, računalništvo in informatiko, Koroška cesta 46, 2000 Maribor 2 Univerza v Mariboru, Fakulteta za naravoslovje in matematiko, Koroška cesta 160, 2000 Maribor E-pošta: danilo.korze@um.si, aleksander.vesel@um.si Radio k-labelings of infinite lattices Abstract. A radio k-labeling of a graph G is an assignment of non-negative integers (labels) to the vertices of G such that the absolute value of the difference between the labels of any two distinct vertices u and v is not less than 𝑘 +1−𝑑 (𝑢 ,𝑣 ), where 𝑑 (𝑢 ,𝑣 ) denotes the distance between u and v. The radio k-labeling number of G is the minimum span of a radio k-labeling of G. Radio k-labelings of four different infinite lattices are considered. Strongly improved upper bounds are presented, mostly using computer-based methods for computing radio k-labelings of these families of graphs. 1 Uvod Predpisi za dodelitev frekvenc za frekvenčno modulirane oddajnike (recimo bazne postaje mobilnega omrežja) so motivirali številne modele na osnovi teorije grafov. Cilj teh modelov je zagotoviti, da dve radijski postaji, ki sta locirani dovolj blizu skupaj druga drugi, oddajata na frekvencah, ki sta dovolj daleč narazen, sicer lahko pride do interference njunih signalov in posledično motenj delovanja. V splošnem so pri uporabi teorije grafov za dodeljevanje radijskih frekvenc sami radijski oddajniki predstavljeni kot vozlišča grafa, medtem ko število povezav na najkrajši poti med dvema vozliščema predstavlja razdaljo med oddajnikoma. Nekateri primeri takih modelov označevanja (barvanja) so radijsko k- barvanje, 𝐿 (𝑠 1 ,𝑠 2 ,⋯,𝑠 𝑞 )-barvanje in pakirno barvanje [1]. Vsi trije omenjeni modeli barvanja grafov so precej zahtevni za reševanje, in to že za relativno preproste grafe, recimo drevesa. V tem članku bomo obravnavali model na osnovi radijskega k-barvanja, ki je bil predlagan v [2]. Naj bo k pozitivno celo število, G pa povezan graf. Razdalja med vozliščema u in v je enaka razdalji najkrajše poti med u in v ter je označena z 𝑑 (𝑢 ,𝑣 ). Radijsko k-barvanje f grafa G je takšna prireditev nenegativnih celih števil posameznim vozliščem, da za vsaki dve vozlišči u in v iz G velja enačba (1). |𝑓 (𝑢 )−𝑓 (𝑣 )|≥𝑘 +1−𝑑 (𝑢 ,𝑣 ) (1) Z oznako rl k(G) označimo minimalni razpon radijskega barvanja grafa G (razlika med največjo in najmanjšo vrednostjo barve v grafu G). Ker običajno pričnemo barvanje z barvo 0, je v tem primeru rl k(G) enak kar največji uporabljeni barvi v grafu. Iz definicije je tudi razvidno, da je recimo radijsko 2-barvanje enako 𝐿 (2,1) barvanju grafa [2]. Ker motivacija za radijsko k-barvanje izhaja iz problema dodeljevanja frekvenc, je pričakovano, da se ozremo na grafe, ki lahko modelirajo različna omrežja: recimo poti in cikle [3, 4], kartezične produkte grafov [5], kvadratne mreže [6] in grafe razdalj [7]. V tem prispevku bomo predstavili radijsko k-barvanje štirih neskončnih mrež: kvadratne ℒ 4, heksagonalne ℒ 3, trikotniške ℒ 6 in oktagonalne mreže ℒ 8 (slika 1). Številka pri oznaki mreže pomeni stopnjo njenih vozlišč. Slika 1. a. kvadratna mreža ℒ4, b. heksagonalna mreža ℒ3, c. trikotniška mreža ℒ6 in d. oktagonalna mreža ℒ8. V nadaljevanju si bomo najprej v 2. poglavju ogledali teoretične osnove (predvsem spodnje in zgornje meje) za radijsko k-barvanje mrež. V 3. poglavju bomo opisali računalniške pristope k temu problemu in dobljene rezultate. Sledil bo še krajši zaključek. 2 Teoretične meje Pri težjih problemih barvanja grafov običajno uporabimo pristop z iskanjem spodnjih in zgornjih mej, v našem primeru radijskega k-barvanja. Spodnje in zgornje meje lahko iščemo s teoretičnim razmislekom in izpeljavo ali pa s konkretno rešitvijo: zgornjo mejo recimo določimo tako, da konstruiramo barvanje grafa, spodnjo pa tako, da pokažemo, da barvanje z nekim številom barv ne obstaja. Teoretične spodnje in zgornje meje za prve tri mreže so bile podane v [8], medtem ko smo spodnjo mejo za oktagonalno mrežo ℒ 8 izpeljali sami z uporabo tehnike, ki je podrobno opisana v že omenjenem članku [8]. Spodnje meje podajajo enačbe (2-5), zgornjo mejo pa enačba (6). Zgornja meja za oktagonalno mrežo ni 306 teoretično izpeljana, je pa gotovo večja od zgornje meje za ostale tri mreže. 𝑟 𝑙 𝑘 (ℒ 6 )≥{ 𝑘 3 +3𝑘 2 +5𝑘 −1 4 , če je k lih, 𝑘 3 +3𝑘 2 +6𝑘 4 , če je k sod. (2) 𝑟𝑙 𝑘 (ℒ 4 )≥{ 𝑘 3 +3𝑘 2 +5𝑘 −3 6 , če je k lih, 𝑘 3 +3𝑘 2 +8𝑘 6 , če je k sod. (3) 𝑟𝑙 𝑘 (ℒ 3 )≥{ 𝑘 3 +3𝑘 2 +10𝑘 8 , če je k lih, 𝑘 3 +3𝑘 2 +7𝑘 −3 8 , če je k sod. (4) 𝑟𝑙 𝑘 (ℒ 8 )≥ 𝑘 3 +3𝑘 2 +5𝑘 3 . (5) Spodnja meja v enačbi (5) velja tako za sode kot lihe vrednosti k. V enačbi (6) podajamo še zgornje meje, ki pa veljajo le za prve tri mreže: 𝑟𝑙 𝑘 (ℒ 3,4,6 )≤ { 5𝑘 3 +17𝑘 2 +28𝑘 16 , k≡0 mod 4, 5𝑘 3 +15𝑘 2 +27𝑘 +1 16 , k≡1 mod 4, 5𝑘 3 +21𝑘 2 +12𝑘 −20 16 , k≡2 mod 4, 5𝑘 3 +19𝑘 2 +23𝑘 −7 16 , k≡3 mod 4. (6) V tabelah 1-4 so izračunane tudi konkretne številske vrednosti teh teoretično določenih mej za vsako mrežo posebej (drugi (SM) in tretji stolpec (ZM)), skupaj z našimi računalniškimi konstrukcijami barvanj (četrti in peti stolpec), ki zgornje meje bistveno izboljšujejo. 3 Opis računalniških metod Reševanja različnih NP-težkih kombinatoričnih problemov, kamor sodijo tudi problemi barvanj grafov, se lahko lotimo s pomočjo računalnika na mnoge načine. Za hiter izračun zgornje meje iskanih vrednosti običajno uporabimo požrešno metodo ali katerega od hevrističnih algoritmov, za natančnejše izračune pa celoštevilsko linearno programiranje ali reševalnik SAT [9], če naštejemo le nekatere pristope. V našem prispevku smo izbrali dva načina računalniškega reševanja radijskega k-barvanja neskončnih mrež: reševalnik SAT (ki je zaradi eksponentne časovne zahtevnosti uporaben le za razmeroma majhne grafe) in posebej zasnovan računalniški program. Opišimo najprej delovanje tega programa, ki nam poišče za izbrano mrežo in izbrano radijsko k-barvanje rešitev s čim manj barvami. Cilj je bil, da najdemo rešitev v čim krajšem času, ni pa nujno, da bo rešitev najboljša možna (z najmanj barvami) za podani graf. Ker si lahko za vse štiri mreže predstavljamo razporeditev vozlišč na način, kot je prikazan na sliki 1, smo si zamislili, da bi iskali barvo 𝑓 (𝑖 ,𝑗 ) vozlišča s koordinatami (𝑖 ,𝑗 ) v obliki enačbe (7): 𝑓 (𝑖 ,𝑗 )=(𝑎 ∗𝑖 +𝑏 ∗𝑗 ) 𝑚𝑜𝑑 𝑑 , (7) kjer sta a in b pozitivni celoštevilski konstanti, 𝑑 −1 pa vrednost največje barve, ki jo bomo morali uporabiti pri barvanju. Vozlišče z indeksoma (0,0) je tem primeru v zgornjem levem kotu izbrane mreže. Iz oblike enačbe (7) izhaja, da bodo bloki barvanj vozlišč potem periodični s periodo d, tako v horizontalni kot vertikalni smeri. Tabela 1. Rezultati radijskega k-barvanja (kvadratna mreža ℒ 4 ), z mastnim tiskom so označene točne vrednosti k SM ZM Rezultat Konstrukcija 𝑓 (𝑖 ,𝑗 ) 1 1 – 1 (i+j) mod 2 2 6 9 6 (2i+4j) mod 7 3 11 23 11 (3i+5j) mod 12 4 24 44 26 (4i+10j) mod 27 5 37 71 37 (7i+11j) mod 38 6 62 118 69 (16i+25j) mod 70 7 87 175 91 (9i+39j) mod 92 8 128 242 144 (9i+61j) mod 145 9 169 319 177 (11i+75j) mod 178 10 230 450 259 (40i+94j) mod 260 Program je razmeroma enostaven: v zanki povečujemo vrednost uporabljenega števila barv d. Za vsak d potem iteriramo še vrednosti a in b med 1 in 𝑑 − 1 ter za vsako kombinacijo a in b preverimo, če je dobljeno barvanje za neko dovolj veliko izbrano mrežo pravilno, torej da ustreza pogojem iz enačbe (1). Ko najdemo pravilno barvanje, smo reševanje za izbrani k in izbrano mrežo zaključili in dobili iskane vrednosti a, b in d. Za poljubno mrežo in izbrani k dobimo rezultat v največ nekaj sekundah. Časovna zahtevnost algoritma je polinomska (približno kvadratično narašča v odvisnosti od d). Tabela 2. Rezultati radijskega k-barvanja (heksagonalna mreža ℒ 3 ), z mastnim tiskom so označene točne vrednosti k SM ZM Rezultat Konstrukcija 𝑓 (𝑖 ,𝑗 ) 1 1 – 1 (i+j) mod 2 2 5 9 5 (3i+2j) mod 6 3 9 23 9 (5i+3j) mod 10 4 19 44 20 (10i+4j) mod 21 5 29 71 33 (11i+7j) mod 34 32 SAT – tabela 5 6 48 118 55 (26i+21j) mod 56 7 67 175 73 (35i+29j) mod 74 8 98 242 114 (19i+54j) mod 115 9 129 319 145 (37i+65j) mod 146 10 175 450 206 (92i+79j) mod 207 Rezultati tako dobljenih rešitev so prikazani v tabelah 1-4. Dokaj presenetljivo je, da so rezultati kljub 307 enostavnosti postopka izjemno dobri. Za majhne vrednosti k je dobljeno število namreč kar enako teoretični spodnji meji, kar pomeni, da bolje ne gre. Tudi za večje vrednosti k so rezultati dokaj blizu teoretičnim spodnjim mejam, v vsakem primeru pa tako dobljene konstrukcije barvanj močno izboljšujejo doslej znane zgornje meje za te mreže. V nadaljevanju smo želeli preveriti, če se da dobljene rešitve še izboljšati. V tem primeru smo kot orodje izbrali reševalnik SAT. Pri tem načinu reševanja kombinatoričnega problema napravimo Booleove izraze v obliki KNO (konjunktivna normalna oblika). Torej imamo na prvem nivoju logične spremenljivke (lahko tudi negirane) povezane z vrati ALI, na drugem nivoju pa so ti izrazi potem povezani z logičnim IN. Poseben program, ki mu pravimo reševalnik SAT (angl. SAT solver), nato poskuša najti takšno kombinacijo nabora spremenljivk, da bo celotni logični izraz resničen oziroma izpolnjiv (angl. SATISFIABLE). Tabela 3. Rezultati radijskega k-barvanja (trikotniška mreža ℒ 6 ), z mastnim tiskom so označene točne vrednosti k SM ZM Rezultat Konstrukcija 𝑓 (𝑖 ,𝑗 ) 1 2 – 2 (i+j) mod 3 2 8 9 8 (2i+3j) mod 9 3 17 23 19 (3i+5j) mod 20 4 34 44 38 (4i+11j) mod 39 5 56 71 62 (7i+11j) mod 63 6 90 118 100 (16i+40j) mod 101 7 131 175 147 (16i+61j) mod 148 8 188 242 208 (28i+44j) mod 209 9 254 319 285 (14i+66j) mod 286 10 340 450 378 (28i+72j) mod 379 Najprej pa moramo seveda zgraditi logični model. Osnova vsega je nabor binarnih spremenljivk. Za naš primer barvanja smo za vsako vozlišče grafa 𝑣 ∈ 𝑉 (𝐺 ) napravili toliko spremenljivk, kot je bilo pričakovano število barv rešitve 𝑠 . Imamo torej nabor logičnih spremenljivk (8): 𝑥 𝑣 ,𝑖 𝑧𝑎 ∀𝑣 ∈𝑉 (𝐺 ) ,𝑖 ∈ {0,1,2,⋯,𝑠 }. (8) Če bo dobljena vrednost spremenljivke 𝑥 𝑣 ,𝑖 =1, bo to pomenilo, da je vozlišče v pobarvano z barvo i. Spremenljivke, ki pomenijo barve, je možno tudi drugače zakodirati v logične spremenljivke, a to bi nam potem zakompliciralo zgradbo modela. Zdaj je treba sestaviti še logične enačbe, ki bodo zagotavljale, da bo njihova rešitev dala tudi pravilno rešitev radijskega k-barvanja. Sestavili smo jih, kot kažejo enačbe (9), (10) in (11). ⋁ 𝑥 𝑣 ,𝑖 ∀𝑣 ∈𝑉 (𝐺 ) 𝑠 𝑖 =0 , (9) ¬𝑥 𝑣 ,𝑖 ∨¬𝑥 𝑣 ,𝑗 𝑣 ∈𝑉 (𝐺 ), 0≤𝑖 <𝑗 ≤𝑠 , (10) ¬𝑥 𝑣 ,𝑖 ∨¬𝑥 𝑢 ,𝑗 𝑣 ,𝑢 ∈𝑉 (𝐺 ),0≤𝑖 <𝑗 ≤𝑠 , |𝑖 −𝑗 |<𝑘 +1−𝑑 (𝑢 ,𝑣 ). (11) Logičnih izrazov tipa (9) imamo toliko, kot je vseh vozlišč grafa in zagotavljajo, da je vsako vozlišče pobarvano z eno od barv. Izrazov tipa (10) je za vsako vozlišče 𝑠 (𝑠 −1)/2, skrbijo pa za to, da isto vozlišče ni pobarvano z dvema različnima barvama hkrati. Logičnih izrazov tipa (11) je največ in njihovega števila se ne da vnaprej čisto točno oceniti, saj so odvisne od grafa oziroma razdalj med vozlišči. Enačbe (11) zagotavljajo, da sta poljubni dve vozlišči lahko pobarvani le s takima dvema barvama, da je izpolnjen pogoj (1). Sistem logičnih enačb (9), (10) in (11) nam radijsko k-barvanje dejansko pretvori v logični test izpolnjivosti. Sistem bo izpolnjiv natanko tedaj, ko bo za pripadajoč graf G obstajalo radijsko k-barvanje. Tabela 4. Rezultati radijskega k-barvanja (oktagonalna mreža ℒ 8 ), z mastnim tiskom so označene točne vrednosti k SM Rezultat Konstrukcija 𝑓 (𝑖 ,𝑗 ) 1 3 3 (i+2j) mod 4 2 10 10 (2i+5j) mod 11 3 23 23 (4i+11j) mod 24 4 44 46 (4i+15j) mod 47 5 75 79 (31i+38j) mod 80 6 118 126 (34i+41j) mod 127 7 175 187 (12i+57j) mod 188 8 248 266 (12i+43j) mod 267 9 339 361 (89i+142j) mod 362 10 450 479 (68i+122j) mod 480 Za realizacijo sistema logičnih enačb (9) do (11) smo potrebne enačbe s pomočjo programa v MATLAB-u zapisali v tekstovno zbirko, ki je bila potem poslana kot vhod v reševalnik SAT. Uporabili smo Cryptominisat5 reševalnik SAT [10], ki se ga da dobiti tako za operacijski sistem Windows, kot tudi Linux. Zadane probleme zna reševati z uporabo več niti, kar nam pridobivanje rešitve bistveno pohitri. Tabela 5. Rešitev z reševalnikom SAT za radijsko 5-barvanje heksagonalne mreže ℒ 3 z maksimalno barvo 32 (ta blok barv se periodično ponavlja horizontalno in vertikalno) Za vsak graf (mrežo), vsak k in vsako končno število barv s moramo napraviti svojo tekstovno zbirko z logičnimi izrazi in jo poslati v reševalnik. Pri tem se postavi vprašanje, kako neskončno mrežo predstaviti s končnim grafom. Pri iskanju barvanja si pomagamo tako, 0 29 12 25 8 21 4 17 0 29 12 25 8 21 4 17 7 20 3 32 15 28 11 24 7 20 3 32 15 28 11 24 14 27 10 23 6 19 2 31 14 27 10 23 6 19 2 31 5 18 1 30 13 26 9 22 5 18 1 30 13 26 9 22 12 25 8 21 4 17 0 29 12 25 8 21 4 17 0 29 3 32 15 28 11 24 7 20 3 32 15 28 11 24 7 20 10 23 6 19 2 31 14 27 10 23 6 19 2 31 14 27 1 30 13 26 9 22 5 18 1 30 13 26 9 22 5 18 8 21 4 17 0 29 12 25 8 21 4 17 0 29 12 25 15 28 11 24 7 20 3 32 15 28 11 24 7 20 3 32 6 19 2 31 14 27 10 23 6 19 2 31 14 27 10 23 13 26 9 22 5 18 1 30 13 26 9 22 5 18 1 30 4 17 0 29 12 25 8 21 4 17 0 29 12 25 8 21 11 24 7 20 3 32 15 28 11 24 7 20 3 32 15 28 2 31 14 27 10 23 6 19 2 31 14 27 10 23 6 19 9 22 5 18 1 30 13 26 9 22 5 18 1 30 13 26 308 da mrežo ciklično povežemo: vozlišča na koncu vsake vrstice pravilno povežemo z vozlišči prvega stolpca, enako tudi vozlišča v zadnji vrstici z vozlišči v prvi vrstici. Dobljeno barvanje tako predstavlja barvanje neskončne mreže. Pri tem je bistveno, kako dolge cikle (vrstice in stolpce) tega grafa smo izbrali. Od tega bo namreč pogosto odvisno, če bo barvanje s takšno periodo in izbranim številom barv sploh obstajalo. Če želimo izboljševati samo spodnjo mejo potrebnega števila barv za barvanje mreže, si lahko pomagamo tudi z manjšim podgrafom neskončne mreže, recimo pri oktagonalni mreži z grafom 𝑃 12 ⊠𝑃 12 . Operator ⊠ pomeni krepki produkt dveh poti, ki je podgraf neskončne oktagonalne mreže ℒ 8. Če za poljuben podgraf grafa G radijsko k-barvanje z določenim številom barv ne obstaja, iz tega sledi, da ne obstaja niti za celoten neskončen graf. Opisani način predstavlja možnost, da se pridobljeni rezultati v nekaterih primerih še izboljšajo. Pri kvadratični mreži smo poskusili izboljšati rezultat za radijsko 4-barvanje, kjer je teoretična spodnja meja 24, z našim preprostim programom pa smo dobili rešitev s 26 barvami. Poskusili smo torej poiskati barvanje s 25 barvami z reševalnikom SAT. Poskus nad kartezičnim produktom dveh poti 𝑃 12 □𝑃 12 , ki je podgraf kvadratne mreže ℒ 4 , se je končal neuspešno, kar pomeni, da je rezultat 26 točna vrednost. Vse točne vrednosti za minimalni razpon barvanja grafa smo v tabelah 1 do 4 (potrjene z reševalnikom SAT) označili z mastnim tiskom. Pri heksagonalni mreži ℒ 3 smo uspeli izboljšati rezultat za radijsko 5-barvanje, periodični blok barvanj z maksimalno barvo 32, najden s pomočjo reševalnika SAT, je v tabeli 5. Model za reševalnik SAT je vseboval 8448 logičnih spremenljivk in 670337 vrstic (disjunkcij), že predhodno pa smo ugotovili, da je perioda ponavljanja barv 16. Poskusili smo še z barvo manj, a se je poskus nad podgrafom velikosti 12×12 vozlišč z reševalnikom SAT končal po dobrih dveh urah neuspešno. 32 je torej točna vrednost za radijsko 5-barvanje heksagonalne mreže ℒ 3 . Pri trikotniški mreži ℒ 6 nam radijskega 3-barvanja ni uspelo izboljšati in smo le potrdili, da je 19 točna rešitev, dobljena z našim enostavnim programom. Tudi cikličnega radijskega 4-barvanja z maksimalno barvo 37 nismo našli, čeprav smo pa recimo z reševalnikom SAT dobili barvanje podgrafa mreže velikosti 60×60 vozlišč. V zvezi z oktagonalno mrežo smo poskusili najti radijsko 4-barvanje z maksimalno barvo 45 podgrafa velikosti 8×8 vozlišč. Izračun se v nekaj dnevih ni zaključil. Rezultate za radijska k-barvanja za k med 1 in 3 pa smo tudi tu potrdili. 4 Zaključek Splošno je znano, da so v tem članku obravnavani tipi barvanja zelo težavni, posledično so uporabljeni postopki časovno zahtevni. Če želimo poiskati radijsko k-barvanje grafa G, je možnih kombinacij barvanja kar 𝑐 |𝑉 (𝐺 )| , kjer je c največja uporabljena barva, |𝑉 (𝐺 )| pa število vozlišč grafa. Že za 𝑐 =20 in 100 vozlišč v grafu je to več kot 100 mestno število možnih kombinacij. Zato je iskanje učinkovitih metod in algoritmov, ki nam ponudijo rešitve, ki so blizu najboljšim možnim, toliko večji izziv. Uspeli smo razviti preprost, hiter in izjemno učinkovit algoritem, ki najde radijska k-barvanja za vse štiri tipe neskončnih mrež. Rešitve smo preverjali tudi z reševalnikom SAT in potrdili, da v večini obravnavanih primerov rezultatov ne moremo izboljšati. Le v primeru heksagonalne mreže smo uspeli najti eno izboljšavo dobljenih rezultatov in sicer pri radijskem 5-barvanju mreže z največjo barvo 32 (naš preprost algoritem je našel barvanje s 33 barvami, le eno barvo več). Predpostavljamo, da so dobljene rešitve v vseh primerih zelo blizu najboljšim možnim. Za male vrednosti k so celo dosežene teoretične spodnje meje. Pri večjih vrednosti k potrebno število barv precej naraste, zato je uporaba drugih metod vprašljiva, saj je računska zahtevnost enostavno prevelika. Predpostavljamo, da bi se morda dali dobiti primerljivi rezultati tudi s kakšnim dobrim hevrističnim postopkom, recimo s prilagojenim simuliranim ohlajanjem, vsekakor pa bi bil čas računanja bistveno daljši. Literatura [1] B. Brešar, S. Klavžar, D. F. Rall: On the packing chromatic number of Cartesian products, hexagonal lattice, and trees, Discrete Applied Mathematics, 155 (2007), 2303-2311. [2] G. Chartrand, D. Erwin, P. Zhang, F. Harary: Radio labelings of graphs, Bull. Inst. Combin. Appl. 33 (2001), 77-85. [3] G. Chartrand, L. Nebeský, P. Zhang: Radio k-colorings of paths, Discuss. Math. Graph Theory 24 (2004), 5-21. [4] D. Liu, X. Zhu: Multi-level distance labelings for paths and cycles, SIAM J. Discrete Mathematics, 19 (2005), 610- 621. [5] M. Kchikech, R. Khennoufa, O. Togni: Radio k-labelings for Cartesian products of graphs, Discuss. Math. Graph Theory 28 (2008), 165-178. [6] T.-S. A. Jiang: The radio number of grid graphs, arXiv:1401.6583v1. [7] R. Čada, J. Ekstein, P. Holub, O. Togni: Radio labelings of distance graphs, Discrete Appl. Math. 161 (2013), 2876- 2884. [8] S. Das, S. C. Ghosh, S. Nandi, S. Sen: A lower bound technique for radio k-coloring, Discrete Mathematics 340 (2017), 855-861. [9] Z. Shao, A. Vesel: Integer linear programming model and satisfiability test reduction for distance constrained labellings of graphs: the case of L(3,2,1) labelling for products of paths and cycles, Communications IET, 7 (2013), 715-720. [10] Cryptominisat5, https://www.msoos.org/cryptominisat5/.