Search the portal

Please enter a term

Full record

Title(d, n)-pakirno barvanje za posplošene grafe Sierpińskega
Title(d, n)-packing coloring of generalized Sierpiński graphs
AuthorJeromel, Anže
Subject(s)Sierpiński; pakirno barvanje; pakirno kromatično število; Sierpiński; packing coloring; packing chromatic number; info:eu-repo/classification/udc/004.94:004.83(043.2)
Abstract

V magistrski nalogi so opisani grafi Sierpińskega in njihove posplošitve, (d, n)-pakirno barvanje grafov ter računsko iskanje (d, n)-pakirnih kromatičnih števil. Razvili smo algoritem za generiranje grafov Sierpińskega z osnovo 4 ter implementirali štiri metode barvanja grafov. Našli smo točna (d, n)-pakirna kromatična števila za različne kombinacije (d, n) pri grafih stopnje 2, pri grafih višjih stopenj pa njihove zgornje meje. Prav tako smo našli točna (1, 1)-pakirna kromatična števila dveh izbranih posplošenih grafov Sierpińskega do vključno stopnje 5.

In our work we describe Sierpiński graphs, their generalizations, (d, n)-packing coloring of graphs and computing their (d, n)-packing chromatic numbers. We developed an algorithm that generates Sierpinski graphs with base 4 and implemented four methods for coloring graphs. We found the exact (d, n)-packing chromatic numbers for different combinations of (d, n) for graphs of dimension 2, and found their upper bounds for graphs of higher dimensions. We also found the exact (1, 1)-packing chromatic numbers for two generalized Sierpiński graphs up to and including dimension 5.

PublisherA. Jeromel
ContributorKorže, Danilo
Date2019-06-04
Typeinfo:eu-repo/semantics/masterThesis; info:eu-repo/semantics/publishedVersion
Identifier
Identifier
Identifier
Languageslv
Formatapplication/pdf
Rightshttp://creativecommons.org/licenses/by-nc-nd/4.0/
Rightsinfo:eu-repo/semantics/openAccess
Relation
AudienceStudents
SourceMaribor