S-packing colorings of cubic graphs

DOI10.1016/J.DISC.2016.04.017zbMATH Open1339.05134arXiv1403.7495OpenAlexW2963947938MaRDI QIDQ294536FDOQ294536

Authors: Nicolas Gastineau, Olivier Togni 

Publication date: 16 June 2016

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: Given a non-decreasing sequence $S=(s_1,s_2,ldots,s_k)$ of positive integers, an {em $S$-packing coloring} of a graph $G$ is a mapping $c$ from $V(G)$ to $s_1,s_2,ldots,s_k$ such that any two vertices with color $s_i$ are at mutual distance greater than $s_i$, $1leilek$. This paper studies $S$-packing colorings of (sub)cubic graphs. We prove that subcubic graphs are $(1,2,2,2,2,2,2)$-packing colorable and $(1,1,2,2,3)$-packing colorable. For subdivisions of subcubic graphs we derive sharper bounds, and we provide an example of a cubic graph of order $38$ which is not $(1,2,ldots,12)$-packing colorable.

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

Recommendations

• On \(S\)-packing edge-colorings of cubic graphs
• Packing colouring of some classes of cubic graphs
• On packing \(S\)-colorings of subcubic graphs
• Packing chromatic number of cubic graphs
• Packing coloring of Sierpiński-type graphs
• Packing coloring of generalized Sierpinski graphs
• Packing \(( 1 , 1 , 2 , 2 )\)-coloring of some subcubic graphs
• Packing colorings of subcubic outerplanar graphs
• Packing chromatic number of subdivisions of cubic graphs
• On the packing coloring of base-3 Sierpiński graphs and \(H\)-graphs

zbMATH Keywords

cubic graphcoloringpacking chromatic number

Mathematics Subject Classification ID

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
• Choosability of the square of planar subcubic graphs with large girth
• A note on packing chromatic number of the square lattice
• Dichotomies properties on computational complexity of \(S\)-packing coloring problems
• A survey on the distance-colouring of graphs
• A note on \(S\)-packing colorings of lattices
• The \(S\)-packing chromatic number of a graph
• Broadcast chromatic numbers of graphs
• 2-distance 4-coloring of planar subcubic graphs
• List-coloring the square of a subcubic graph
• Some large graphs with given degree and diameter
• On the packing chromatic number of Cartesian products, hexagonal lattice, and trees
• Complexity of the packing coloring problem for trees
• On the packing chromatic number of some lattices

Cited In (32)

• Facial packing vertex-coloring of subdivided plane graphs
• Packing colouring of some classes of cubic graphs
• An infinite family of subcubic graphs with unbounded packing chromatic number
• Packing chromatic number versus chromatic and clique number
• A survey on packing colorings
• \(S\)-packing colorings of distance graphs \(G ( \mathbb{Z} , \{ 2 , t \} )\)
• Packing chromatic number of windmill related graphs and chain silicate networks
• Every subcubic multigraph is (1,27) $(1,{2}^{7})$‐packing edge‐colorable
• The exponential growth of the packing chromatic number of iterated Mycielskians
• On packing \(S\)-colorings of subcubic graphs
• Independence number and packing coloring of generalized Mycielski graphs
• Packing \(( 1 , 1 , 2 , 4 )\)-coloring of subcubic outerplanar graphs
• Packing coloring of Sierpiński-type graphs
• On the packing coloring of base-3 Sierpiński graphs and \(H\)-graphs
• About \(S\)-packing coloring of 3-irregular subcubic graphs
• Packing chromatic number of cubic graphs
• About \(S\)-packing coloring of subcubic graphs
• On \(S\)-packing edge-colorings of cubic graphs
• Packing chromatic number of subdivisions of cubic graphs
• On \(S\)-packing coloring of 2-saturated subcubic graphs
• Partial packing coloring and quasi-packing coloring of the triangular grid
• Gröbner bases techniques for an \(S\)-packing \(k\)-coloring of a graph
• Packing \(( 1 , 1 , 2 , 2 )\)-coloring of some subcubic graphs
• Packing colorings of subcubic outerplanar graphs
• On the packing chromatic number of subcubic outerplanar graphs
• On \(S\)-packing edge-colorings of graphs with small edge weight
• Packing chromatic number, \((1, 1, 2, 2)\)-colorings, and characterizing the Petersen graph
• Packing chromatic number under local changes in a graph
• \(S\)-packing chromatic vertex-critical graphs
• On \(S\)-packing colourings of distance graphs \(D (1, t)\) and \(D (1, 2, t)\)
• Packing chromatic numbers of finite super subdivisions of graphs
• \(S\)-packing coloring of cubic Halin graphs

This page was built for publication: \(S\)-packing colorings of cubic graphs

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