755 KB85 KB200820252017Jarnicki, WitoldMyrvold, WendySaltzman, PeterWagon, Stanletnik:13številka:2str. 427-460COBISSID:18368601ISSN:1855-3966URN:URN:NBN:SI:doc-54Q5S2MRenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneabarvanje povezavgrafi MycielskegaKellerjevi grafikraljičini grafiProperties, proved and conjectured, of Keller, Mycielski, and queen graphs|We prove several results about three families of graphs. For queen graphs, defined from the usual moves of a chess queen, we find the edge-chromatic number in almost all cases. In the unproved case, we have a conjecture supported by a vast amount of computation, which involved the development of a new edge-coloring algorithm. The conjecture is that the edge-chromatic number is the maximum degree, except when simple arithmetic forces the edge-chromatic number to be one greater than the maximum degree. For Mycielski graphs, we strengthen an old result that the graphs are Hamiltonian by showing that they are Hamilton-connected (except ?$M_3$?, which is a cycle). For Keller graphs ?$G_d$?, we establish, in all cases, the exact value of the chromatic number, the edge-chromatic number, and the independence number; and we get the clique covering number in all cases except ?$5 \leq d \leq 7$?. We also investigate Hamiltonian decompositions of Keller graphs, obtaining them up to ?$G_6$?Dokažemo več rezultatov o treh družinah grafov. Za kraljičine grafe, definirane z običajnimi premiki šahovske kraljice, najdemo povezavno barvno število v skoraj vseh primerih. Za nedokazani primer imamo domnevo, podprto z ogromno količino izračunov, ki je zahtevala razvoj novega algoritma za barvanje povezav. Domneva pravi, da je povezavno kromatsko število enako maksimalni stopnji, razen kadar mora biti zaradi enostavne aritmetike povezavno barvno število za eno večje od maksimalne stopnje. Za grafe Mycielskega izboljšamo stari rezultat, po katerem so ti grafi hamiltonski in pokažemo, da so hamiltonsko povezani (z izjemo ?$M_3$?, ki je cikel). Za Kellerjeve grafe ?$G_d$? dobimo, v vseh primerih, natančne vrednosti barvnega števila, povezavno barvnega števila, in neodvisnostnega števila; dobimo tudi število pokritja klik v vseh primerih razen za ?$5 \leq d \leq 7$?. Raziskujemo tudi hamiltonske razstavitve Kellerjevih grafov, in jih dobimo vse do ?$G_6$?TEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije