1. A survey on packing coloringsBoštjan Brešar, Jasmina Ferme, Sandi Klavžar, Douglas F. Rall, 2020, review article 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... |
2. Properties of large 2-crossing-critical graphsDrago Bokal, Markus Chimani, Alexander Nover, Jöran Schierbaum, Tobias Stolzmann, Mirko H. Wagner, Tilo Wiedera, 2022, original scientific article Keywords: crossing number, crossing-critical graph, chromatic number, chromatic index, treewidth Published in DKUM: 04.02.2025; Views: 0; Downloads: 4
Full text (882,75 KB) This document has many files! More... |
3. The independence coloring game on graphsBoštjan Brešar, Daša Mesarič Štesl, 2022, original scientific article 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... |
4. On b-acyclic chromatic number of a graphMarcin Anholcer, Sylwia Cichacz, Iztok Peterin, 2023, original scientific article Abstract: Let ▫$G$▫ be a graph. We introduce the acyclic b-chromatic number of ▫$G$▫ as an analog to the b-chromatic number of ▫$G$▫. An acyclic coloring of a graph ▫$G$▫ is a map ▫$c:V(G)\rightarrow \{1,\dots,k\}$▫ such that ▫$c(u)\neq c(v)$▫ for any ▫$uv\in E(G)$▫ and the induced subgraph on vertices of any two colors ▫$i,j\in \{1,\dots,k\}$▫ induce a forest. On a set of all acyclic colorings of a graph ▫$G$▫ we define a relation whose transitive closure is a strict partial order. The minimum cardinality of its minimal element is then the acyclic chromatic number ▫$A(G)$▫ of ▫$G$▫ and the maximum cardinality of its minimal element is the acyclic b-chromatic number ▫$A_b(G)$▫ of ▫$G$▫. We present several properties of ▫$A_b(G)$▫. In particular, we derive ▫$A_b(G)$▫ for several known graph families, derive some bounds for ▫$A_b(G)$▫, compare ▫$A_b(G)$▫ with some other parameters and generalize some influential tools from b-colorings to acyclic b-colorings. Keywords: acyclic b-chromatic number, acyclic coloring, b-coloring Published in DKUM: 02.08.2023; Views: 421; Downloads: 15
Full text (585,63 KB) This document has many files! More... |
5. A note on the chromatic number of the square of the Cartesian product of two cyclesZehui Shao, Aleksander Vesel, 2013, other scientific articles 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 |
6. On the b-chromatic number of some graph productsMarko Jakovac, Iztok Peterin, 2012, original scientific article Abstract: Pravilno barvanje vozlišč grafa kjer vsak barvni razred vsebuje vozlišče, ki ima soseda v vseh preostalih barvnih razredih, imenujemo b-barvanje. Največje naravno število ▫$varphi (G)$▫, za katero obstaja b-barvanje grafa ▫$G$▫, imenujemo b-kromatično število. Določimo nekatere spodnje in zgornje meje b-kromatičnega števila za krepki produkt ▫$G,boxtimes, H$▫, leksikografski produkt ▫$G[H]$▫ in za direktni produkt ▫$G,times, H$▫. Prav tako določimo nekatere točne vrednosti za produkte poti, ciklov, zvezd in polnih dvodelnih grafov. Pokažemo tudi, da lahko določimo b-kromatično število za ▫$P_n ,boxtimes, H$▫, ▫$C_n ,boxtimes, H$▫, ▫$P_n[H]$▫, ▫$C_n[H]$▫ in ▫$K_{m,n}[H]$▫ za poljuben graf ▫$H$▫, če sta le ▫$m$▫ in ▫$n$▫ dovolj veliki. Keywords: teorija grafov, b-kromatično število, krepki produkt, leksikografski produkt, direktni produkt, graph theory, b-chromatic number, strong product, lexicographic product, direct product Published in DKUM: 10.07.2015; Views: 1190; Downloads: 90
Link to full text |
7. The distinguishing chromatic number of Cartesian products of two complete graphsJanja Jerebic, Sandi Klavžar, 2010, published scientific conference contribution 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 |
8. The b-chromatic number of cubic graphsMarko Jakovac, Sandi Klavžar, 2010, original scientific article Abstract: b-Kromatično število grafa ▫$G$▫ je največje celo število, za katero obstaja dobro ▫$k$▫-barvanje, v katerem vsak barvni razred vsebuje vsaj eno vozlišče, ki je sosednje z vsemi drugimi barvnimi razredi. Dokazano je, da je b-kromatično število kubičnih grafov enako 4 razen za Petersenov graf, ▫$K_{3,3}$▫, prizmo nad ▫$K_3$▫, in še en sporadičen primer na 10 vozliščih. Keywords: teorija grafov, kromatično število, b-kromatično število, kubični graf, Petersenov graf, graph theory, chromatic number, b-chromatic number, cubic graph, Petersen graph Published in DKUM: 10.07.2015; Views: 1048; Downloads: 96
Link to full text |
9. Vertex-, edge-, and total-colorings of Sierpiński-like graphsMarko Jakovac, Sandi Klavžar, 2009, original scientific article 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 |
10. A 2-parametric generalization of Sierpiński gasket graphsMarko Jakovac, 2009 Abstract: Graphs ▫$S[n,k]$▫ are introduced as the graphs obtained from the Sierpiński graphs ▫$S(n,k)$▫ by contracting edges that lie in no triangle. The family ▫$S[n,k]$▫ is a previously studied class of Sierpiñski gasket graphs ▫$S_n$▫. Several properties of graphs ▫$S[n,k]$▫ are studied in particular, hamiltonicity and chromatic number. Keywords: teorija grafov, kromatično število, Sierpińskijev graf, graph theory, chromatic number, Sierpiński graphs, Sierpiński gasket graphs, hamiltonicity Published in DKUM: 10.07.2015; Views: 1212; Downloads: 54
Link to full text |