Packing coloring of some undirected and oriented coronae graphs

DOI10.7151/DMGT.1963MaRDI QIDQ2364089zbMATH OpenOpenAlexFDO

Authors Daouya Laïche, Isma Bouchemakh, Éric Sopena

Publication date 17 July 2017

Published in Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported

Full work available at URL https://arxiv.org/abs/1506.07248

zbMATH Keywords

cyclepathpacking chromatic numberpacking coloringcorona graph

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: 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$, $1leilek$. For a given integer $pge1$, the generalized corona $Godotp{K}_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.

Recommendations

• Packing chromatic number of certain fan and wheel related graphs
• On the packing coloring of undirected and oriented generalized theta graphs
• On packing coloring of helm related graphs
• Packing coloring of generalized Sierpinski graphs
• On packing colorings of distance graphs

Cites work

• scientific article; zbMATH DE number 2104737 (Why is no real title available?)
• A note on packing chromatic number of the square lattice
• Broadcast chromatic numbers of graphs
• Complexity of the Packing Coloring Problem for Trees
• Dichotomies properties on computational complexity of \(S\)-packing coloring problems
• On packing colorings of distance graphs
• On the Packing Chromatic Number of Trees, Cartesian Products and Some Infinite Graphs
• On the packing chromatic number of Cartesian products, hexagonal lattice, and trees
• On the packing chromatic number of some lattices
• On the packing chromatic number of square and hexagonal lattice
• Packing chromatic number of distance graphs
• Polynomial instances of the packing coloring problem
• The packing chromatic number of hypercubes
• The packing chromatic number of infinite product graphs
• The packing coloring of distance graphs \(D(k,t)\)
• The packing coloring problem for \((q,q-4)\) graphs
• The packing coloring problem for lobsters and partner limited graphs

Cited in

(14)

• A survey on packing colorings
• Packing \(( 1 , 1 , 2 , 4 )\)-coloring of subcubic outerplanar graphs
• Neighbor sum distinguishing total colorings of corona of subcubic graphs
• On \(S\)-packing coloring of 2-saturated subcubic graphs
• About \(S\)-packing coloring of subcubic graphs
• Packing chromatic number of subdivisions of cubic graphs
• \(S\)-packing coloring of cubic Halin graphs
• On packing \(S\)-colorings of subcubic graphs
• On the packing coloring of undirected and oriented generalized theta graphs
• About \(S\)-packing coloring of 3-irregular subcubic graphs
• Packing \(( 1 , 1 , 2 , 2 )\)-coloring of some subcubic graphs
• Packing colouring of some classes of cubic graphs
• Graphs that are critical for the packing chromatic number
• Packing chromatic number of cubic graphs

This page was built for publication: Packing coloring of some undirected and oriented coronae graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2364089)