Search the digital library catalog

Abstract: If S=(a1,a2,...) is a non-decreasing sequence of positive integers, then an S-packing coloring of a graph G is a partition of V (G) into sets X1,X2,... such that for each pair of distinct vertices in the set Xi, the distance between them is larger than ai. If there exists an integer k such that V(G)=X1 U ... U Xk, then the partition is called an S-packing k-coloring. The S-packing chromatic number of G is the smallest k such that G admits an S-packing k-coloring. If ai=i for every i, then the terminology reduces to packing colorings and packing chromatic number. Since the introduction of these generalizations of the chromatic number in 2008 more than fifty papers followed. Here we survey the state of the art on the packing coloring, and ts generalization, the S-packing coloring. We also list several conjecres and open problems.
Keywords: packing coloring, packing chromatic number, subcubic graph, S-packing chromatic number, computational complexity
Published in DKUM: 11.03.2025; Views: 0; Downloads: 7
Full text (98,49 KB)
This document has many files! More...

Abstract: We propose a new coloring game on a graph, called the independence coloring game, which is played by two players with opposite goals. The result of the game is a proper coloring of vertices of a graph G, and Alice’s goal is that as few colors as possible are used during the game, while Bob wants to maximize the number of colors. The game consists of rounds, and in round i, where i = 1, 2,, … , the players are taking turns in selecting a previously unselected vertex of G and giving it color i (hence, in each round the selected vertices form an independent set). The game ends when all vertices of G are selected (and thus colored), and the total number of rounds during the game when both players are playing optimally with respect to their goals, is called the independence game chromatic number, χig(G), of G. In fact, four different versions of the independence game chromatic number are considered, which depend on who starts a game and who starts next rounds. We prove that the new invariants lie between the chromatic number of a graph and the maximum degree plus 1, and characterize the graphs in which each of the four versions of the game invariant equals 2. We compare the versions of the independence game chromatic number among themselves and with the classical game chromatic number. In addition, we prove that the independence game chromatic number of a tree can be arbitrarily large.
Keywords: graph, coloring, coloring game, competition-independence game, game chromatic number, tree
Published in DKUM: 09.08.2024; Views: 99; Downloads: 10
Full text (852,33 KB)
This document has many files! More...

Abstract: The square ▫$G^2$▫ of a graph ▫$G$▫ is obtained from ▫$G$▫ by adding edges joining all pairs of nodes at distance 2 in ▫$G$▫. In this note we prove that ▫$chi((C_mBox C_n)^2) le 6$ for $m, n ge 40$▫. This confirms Conjecture 19 stated in [É. Sopena, J. Wu, Coloring the square of the Cartesian product of two cycles, Discrete Math. 310 (2010) 2327-2333].
Keywords: matematika, teorija grafov, kromatično število, kartezični produkt, označevanje grafov, kvadrat grafa, mathematics, graph theory, chromatic number, Cartesian product, graph labeling, square if a graph
Published in DKUM: 10.07.2015; Views: 1460; Downloads: 84
Link to full text

Abstract: Označitev grafa ▫$G$▫ je razlikovalna, če jo ohranja le trivialni avtomorfizem grafa ▫$G$▫. Razlikovalno kromatično število grafa ▫$G$▫ je najmanjše naravno število, za katero obstaja razlikovalna označitev grafa, ki je hkrati tudi dobro barvanje. Za vse ▫$k$▫ in ▫$n$▫ je določeno razlikovalno kromatično število kartezičnih produktov ▫$K_kBox K_n$▫. V večini primerov je enako kromatičnemu številu, kar med drugim odgovori na vprašanje Choia, Hartkeja and Kaula, ali obstajajo še kakšni drugi grafi, za katere velja enakost.
Keywords: teorija grafov, razlikovalno kromatično število, grafovski avtomorfizem, kartezični produkt grafov, graph theory, distinguishing chromatic number, graph automorphism, Cartesian product of graphs
Published in DKUM: 10.07.2015; Views: 1152; Downloads: 97
Link to full text

Abstract: Obravnavana so vozliščna, povezavna in skupna barvanja grafov Sierpińskijevih rešetk ▫$S_n$▫, Sierpińskijevih grafov ▫$S(n,k)$▫, grafov ▫$S^+(n,k)$▫ in grafov ▫$S^{++}(n,k)$▫. V posebnem je dokazano, da velja ▫$chi''(S_n)$▫, ▫$chi'(S(n,k))$▫, ▫$chi(S^+(n,k))$▫, ▫$chi(S^{++}(n,k))$▫, ▫$chi'(S^+(n,k))$▫ in ▫$chi'(S^{++}(n,k))$▫.
Keywords: matematika, teorija grafov, Sierpińskijeve rešetke, Sierpińskijevi grafi, kromatično število, kromatični indeks, skupno kromatično število, mathematics, graph theory, Sierpiński gasket graphs, Sierpiński graphs, chromatic number, chromatic index, total chromatic number
Published in DKUM: 10.07.2015; Views: 1075; Downloads: 96
Link to full text