Results 1 to 10 of about 254,850 (275)
Independence Number and Packing Coloring of Generalized Mycielski Graphs
Discussiones Mathematicae Graph Theory, 2021 For a positive integer k ⩾ 1, a graph G with vertex set V is said to be k-packing colorable if there exists a mapping f : V ↦ {1, 2, . . ., k} such that any two distinct vertices x and y with the same color f(x) = f(y) are at distance at least f(x) + 1 ...
Bidine Ez Zobair +2 more
doaj +5 more sources
Notes on complexity of packing coloring [PDF]
Information Processing Letters, 2018 A packing $k$-coloring for some integer $k$ of a graph $G=(V,E)$ is a mapping $\varphi:V\to\{1,\ldots,k\}$ such that any two vertices $u, v$ of color $\varphi(u)=\varphi(v)$ are in distance at least $\varphi(u)+1$.
Minki Kim +3 more
semanticscholar +11 more sources
Packing coloring of generalized Sierpinski graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2019 The packing chromatic number $\chi_{\rho}(G)$ of a graph $G$ is the smallest integer $c$ such that the vertex set $V(G)$ can be partitioned into sets $X_1, . . .
Danilo Korze, Aleksander Vesel
doaj +6 more sources
On distance dominator packing coloring in graphs
Discussiones Mathematicae Graph Theory, 2021 Let G be a graph and let S = (s1,s2,..., sk) be a non-decreasing sequence of positive integers. An S-packing coloring of G is a mapping c : V(G) ? {1, 2,..., k} with the following property: if c(u) = c(v) = i, then d(u,v) > si for any i ? {1, 2,...,k}.
Jasmina Ferme, Daša Štesl
semanticscholar +6 more sources
On packing colorings of distance graphs [PDF]
Discrete Applied Mathematics, 2013 The {\em packing chromatic number} $\chi_{\rho}(G)$ of a graph $G$ is the least integer $k$ for which there exists a mapping $f$ from $V(G)$ to $\{1,2,\ldots ,k\}$ such that any two vertices of color $i$ are at distance at least $i+1$. This paper studies
Olivier Togni
core +8 more sources
Packing coloring of Sierpiński-type graphs [PDF]
Aequationes Mathematicae, 2017 Boštjan Brešar, Jasmina Ferme
semanticscholar +5 more sources
Packing Coloring of Some Undirected and Oriented Coronae Graphs [PDF]
Discussiones Mathematicae Graph Theory, 2017 The packing chromatic number χρ(G) of a graph G is the smallest integer k such that its set of vertices V(G) can be partitioned into k disjoint subsets V1, . . . , Vk, in such a way that every two distinct vertices in Vi are at distance greater than i in
Laïche Daouya +2 more
doaj +2 more sources
Online vector bin packing and hypergraph coloring illuminated: simpler proofs and new connections [PDF]
Latin-American Algorithms, Graphs and Optimization Symposium, 2023 This paper studies the online vector bin packing (OVBP) problem and the related problem of online hypergraph coloring (OHC). Firstly, we use a double counting argument to prove an upper bound of the competitive ratio of $FirstFit$ for OVBP.
Yaqiao Li, Denis Pankratov
semanticscholar +4 more sources
Further results and questions on S-packing coloring of subcubic graphs
Discrete MathematicsFor non-decreasing sequence of integers $S=(a_1,a_2, \dots, a_k)$, an $S$-packing coloring of $G$ is a partition of $V(G)$ into $k$ subsets $V_1,V_2,\dots,V_k$ such that the distance between any two distinct vertices $x,y \in V_i$ is at least $a_{i}+1$, $
Maidoun Mortada, Olivier Togni
semanticscholar +3 more sources
Graph Coloring Below Guarantees via Co-Triangle Packing [PDF]
International Symposium on Algorithms and ComputationIn the $\ell$-Coloring Problem, we are given a graph on $n$ nodes, and tasked with determining if its vertices can be properly colored using $\ell$ colors. In this paper we study below-guarantee graph coloring, which tests whether an $n$-vertex graph can
Akmal, Shyan, Koana, Tomohiro
openalex +2 more sources