Packing coloring of some undirected and oriented coronae graphs

DOI10.7151/DMGT.1963zbMATH Open1366.05044arXiv1506.07248OpenAlexW2963304639MaRDI QIDQ2364089FDOQ2364089

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

Publication date: 17 July 2017

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

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.

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

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

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)

Cites Work

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

Cited In (14)

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