
arXiv: 1506.07248
The packing chromatic number $\pcn(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 $V\_1$, \ldots, $V\_k$, in such a way that every two distinct vertices in $V\_i$ are at distance greater than $i$ in $G$ for every $i$, $1\le i\le k$. For a given integer $p \ge 1$, the generalized corona $G\odot pK\_1$ of a graph $G$ is the graph obtained from $G$ by adding $p$ degree-one neighbors to every vertex of $G$. In this paper, we determine the packing chromatic number of generalized coronae of paths and cycles. Moreover, by considering digraphs and the (weak) directed distance between vertices, we get a natural extension of the notion of packing coloring to digraphs. We then determine the packing chromatic number of orientations of generalized coronae of paths and cycles.
FOS: Computer and information sciences, 05c70, Discrete Mathematics (cs.DM), cycle, Packing coloring, Corona graph, path, Cycle, packing coloring, Trees, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], packing chromatic number, Coloring of graphs and hypergraphs, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), 05c15, 05c05, QA1-939, Path, corona graph, Mathematics, Packing chromatic number, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, 05c70, Discrete Mathematics (cs.DM), cycle, Packing coloring, Corona graph, path, Cycle, packing coloring, Trees, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], packing chromatic number, Coloring of graphs and hypergraphs, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), 05c15, 05c05, QA1-939, Path, corona graph, Mathematics, Packing chromatic number, Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 10 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
