1. The independence coloring game on graphsBoštjan Brešar, Daša Mesarič Štesl, 2022, izvirni znanstveni članek Opis: 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.
Ključne besede: graph, coloring, coloring game, competition-independence game, game chromatic number, tree
Objavljeno v DKUM: 09.08.2024; Ogledov: 88; Prenosov: 3
 Celotno besedilo (852,33 KB)
Gradivo ima več datotek! Več... |
2. On b-acyclic chromatic number of a graphMarcin Anholcer, Sylwia Cichacz, Iztok Peterin, 2023, izvirni znanstveni članek Opis: 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.
Ključne besede: acyclic b-chromatic number, acyclic coloring, b-coloring
Objavljeno v DKUM: 02.08.2023; Ogledov: 407; Prenosov: 12
Celotno besedilo (585,63 KB)
Gradivo ima več datotek! Več... |
3. A note on the chromatic number of the square of the Cartesian product of two cyclesZehui Shao, Aleksander Vesel, 2013, drugi znanstveni članki Opis: 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].
Ključne besede: 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
Objavljeno v DKUM: 10.07.2015; Ogledov: 1449; Prenosov: 83
 Povezava na celotno besedilo |
4. On the b-chromatic number of some graph productsMarko Jakovac, Iztok Peterin, 2012, izvirni znanstveni članek Opis: 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.
Ključne besede: teorija grafov, b-kromatično število, krepki produkt, leksikografski produkt, direktni produkt, graph theory, b-chromatic number, strong product, lexicographic product, direct product
Objavljeno v DKUM: 10.07.2015; Ogledov: 1179; Prenosov: 89
Povezava na celotno besedilo |
5. The distinguishing chromatic number of Cartesian products of two complete graphsJanja Jerebic, Sandi Klavžar, 2010, objavljeni znanstveni prispevek na konferenci Opis: 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.
Ključne besede: teorija grafov, razlikovalno kromatično število, grafovski avtomorfizem, kartezični produkt grafov, graph theory, distinguishing chromatic number, graph automorphism, Cartesian product of graphs
Objavljeno v DKUM: 10.07.2015; Ogledov: 1140; Prenosov: 94
Povezava na celotno besedilo |
6. The b-chromatic number of cubic graphsMarko Jakovac, Sandi Klavžar, 2010, izvirni znanstveni članek Opis: 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.
Ključne besede: 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
Objavljeno v DKUM: 10.07.2015; Ogledov: 1036; Prenosov: 94
Povezava na celotno besedilo |
7. Vertex-, edge-, and total-colorings of Sierpiński-like graphsMarko Jakovac, Sandi Klavžar, 2009, izvirni znanstveni članek Opis: 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))$▫.
Ključne besede: 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
Objavljeno v DKUM: 10.07.2015; Ogledov: 1073; Prenosov: 95
Povezava na celotno besedilo |
8. A 2-parametric generalization of Sierpiński gasket graphsMarko Jakovac, 2009 Opis: 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.
Ključne besede: teorija grafov, kromatično število, Sierpińskijev graf, graph theory, chromatic number, Sierpiński graphs, Sierpiński gasket graphs, hamiltonicity
Objavljeno v DKUM: 10.07.2015; Ogledov: 1207; Prenosov: 53
Povezava na celotno besedilo |
9. Game chromatic number of Cartesian product graphsT. Bartnicki, Boštjan Brešar, J. Grytczuk, Matjaž Kovše, Z. Miechowicz, Iztok Peterin, 2008, izvirni znanstveni članek Opis: Obravnavamo igralno kromatično število ▫$chi_g$▫ kartezičnega produkta ▫$G Box H$▫ dveh grafov ▫$G$▫ in ▫$H$▫. Določimo točne vrednosti za ▫$chi_g(K_2 Box H$▫, ko je ▫$H$▫ pot, cikel ali poln graf. S pomočjo novo vpeljane "igre kombinacij" pokažemo, da igralno kromatično število ni omejeno znotraj razreda kartezičnih produktov dveh polnih dvodelnih grafov. Iz tega rezultata sledi, da igralno kromatično število ▫$chi_g(G Box H$▫ ni navzgor omejeno s kako funkcijo igralnih kromatičnih števil grafov ▫$G$▫ in ▫$H$▫. Analogen rezultat je izpeljan za igralno barvno število kartezičnih produktov grafov.
Ključne besede: matematika, teorija grafov, kartezični produkt grafov, igralno kromatično število, mathematics, graph theory, Cartesian prodict, game chromatic number
Objavljeno v DKUM: 10.07.2015; Ogledov: 1134; Prenosov: 256
Povezava na celotno besedilo |
10. On the packing chromatic number of Cartesian products, hexagonal lattice, and treesBoštjan Brešar, Sandi Klavžar, Douglas F. Rall, 2007, izvirni znanstveni članek Opis: Pakirno kromatično število ▫$chi_{rho}(G)$▫ grafa ▫$G$▫ je najmanjše število ▫$k$▫, tako da lahko množico vozlišč grafa ▫$G$▫ razbijemo v pakiranja s paroma različnimi širinami. Dobljenih je več spodnjih in zgornjih meja za pakirno kromatično število kartezičnega produkta grafov. Dokazano je, da pakirno kromatično število šestkotniške mreže leži med 6 in 8. Optimalne spodnje in zgornje meje so dokazane za subdividirane grafe. Obravnavana so tudi drevesa ter vpeljana monotona barvanja.
Ključne besede: matematika, teorija grafov, pakirno kromatično število, kartezični produkt grafov, šestkotniška mreža, subdividiran graf, drevo, računska zahtevnost, mathematics, graph theory, packing chromatic number, Cartesian product of graphs, hexagonal lattice, subdivision graph, tree, computational complexity
Objavljeno v DKUM: 10.07.2015; Ogledov: 1308; Prenosov: 156
Povezava na celotno besedilo |
