Pakirna barvanja nekaterih razredov grafov z rekurzivno strukturo : doktorska disertacija

slovenian

doktorska dela

2022

coloring   critical graph   cubic graph   doctoral theses   packing chromatic critical graph   packing chromatic number   packing chromatic-vertex critical graph   packing coloring   Sierpiński graph   Sierpiński triangle graph

Univerza v Mariboru, Fakulteta za naravoslovje in matematiko

In this dissertation, packing colorings of graphs are studied. These colorings are among very well studied variants of graph colorings. The dissertation consists of three parts, in which we present solutions of various problems related to packing colorings. The common ground of the mentioned problems is that in their treatment graphs with a recursive structure appear. These graphs are the basis of a given open question, its solution or their recursive structure is an important tool of proving results. In the first part of the dissertation, we present an infinite family of subcubic graphs with unbounded packing chromatic number. An additional property of the mentioned family of graphs is its recursive structure. By providing this family of graphs, we complete the solution to a question that was open for several years regarding the boundedness of the packing chromatic number in the family of subcubic graphs. In the second part, we determine the packing chromatic numbers (or bounds for them) of Sierpiński type graphs, which form a well-known class of graphs with recursive (fractal) structure. We consider Sierpiński graphs, generalized Sierpiński graphs and Sierpiński triangle graphs. The last part of the dissertation is devoted to the graphs that are critical for the packing chromatic number. Among other things, we present characterizations ofpacking chromatic critical graphs with small packing chromatic numbers and discuss packing chromatic critical block graphs.

08.08.2023