Packing ( 1 , 1 , 2 , 2 )-coloring of some subcubic graphs

DOI10.1016/J.DAM.2020.03.015zbMATH Open1442.05063arXiv1911.03824OpenAlexW3011206457MaRDI QIDQ2192116FDOQ2192116

Authors: Runrun Liu, Xujun Liu, Martin Rolek, Gexin Yu 

Publication date: 29 June 2020

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

Abstract: For a sequence of non-decreasing positive integers $S=(s_1,ldots,s_k)$, a packing $S$-coloring is a partition of $V(G)$ into sets $V_1,ldots,V_k$ such that for each $1leqileqk$ the distance between any two distinct $x,yin{V}_i$ is at least $s_i+1$. The smallest $k$ such that $G$ has a packing $(1,2,ldots,k)$-coloring is called the packing chromatic number of $G$ and is denoted by $ch{i}_p(G)$. For a graph $G$, let $D(G)$ denote the graph obtained from $G$ by subdividing every edge. The question whether $ch{i}_p(D(G))le5$ for all subcubic graphs was first asked by Gastineau and Togni and later conjectured by Bresar, Klavzar, Rall and Wash. Gastineau and Togni observed that if one can prove every subcubic graph except the Petersen graph is packing $(1,1,2,2)$-colorable then the conjecture holds. The maximum average degree, mad($G$), is defined to be $maxfrac2|E(H)||V(H)|:HsubsetG$. In this paper, we prove that subcubic graphs with $mad(G)<frac3011$ are packing $(1,1,2,2)$-colorable. As a corollary, the conjecture of Bresar et al holds for every subcubic graph $G$ with $mad(G)<frac3011$.

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

Recommendations

• Packing chromatic number of subdivisions of cubic graphs
• \(S\)-packing colorings of cubic graphs
• Packing chromatic number, \((1, 1, 2, 2)\)-colorings, and characterizing the Petersen graph
• Packing \(( 1 , 1 , 2 , 4 )\)-coloring of subcubic outerplanar graphs
• On packing \(S\)-colorings of subcubic graphs

zbMATH Keywords

independent setssubcubic graphsmaximum average degreepacking coloring

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15)

Cites Work

• The packing chromatic number of infinite product graphs
• Packing chromatic number of cubic graphs
• Packing chromatic number of subdivisions of cubic graphs
• Dichotomies properties on computational complexity of \(S\)-packing coloring problems
• A note on \(S\)-packing colorings of lattices
• The \(S\)-packing chromatic number of a graph
• \(S\)-packing colorings of cubic graphs
• Broadcast chromatic numbers of graphs
• 2-distance 4-coloring of planar subcubic graphs
• On the packing chromatic number of Cartesian products, hexagonal lattice, and trees
• Complexity of the packing coloring problem for trees
• Facial packing edge-coloring of plane graphs
• On the packing chromatic number of square and hexagonal lattice
• The packing chromatic number of hypercubes
• Packing chromatic number versus chromatic and clique number
• Title not available (Why is that?)
• The packing coloring problem for lobsters and partner limited graphs
• Packing chromatic number of base-3 Sierpiński graphs
• Packing Coloring of Undirected and Oriented Generalized Theta Graphs
• Packing chromatic number, \((1, 1, 2, 2)\)-colorings, and characterizing the Petersen graph
• Packing chromatic number under local changes in a graph
• An infinite family of subcubic graphs with unbounded packing chromatic number
• On the packing chromatic number of subcubic outerplanar graphs
• Packing coloring of some undirected and oriented coronae graphs

Cited In (11)

• \(S\)-packing colorings of cubic graphs
• A survey on packing colorings
• \(S\)-packing colorings of distance graphs \(G ( \mathbb{Z} , \{ 2 , t \} )\)
• Every subcubic multigraph is (1,27) $(1,{2}^{7})$‐packing edge‐colorable
• On packing \(S\)-colorings of subcubic graphs
• Packing \(( 1 , 1 , 2 , 4 )\)-coloring of subcubic outerplanar graphs
• About \(S\)-packing coloring of 3-irregular subcubic graphs
• A characterization of 4-\(\chi_S\)-vertex-critical graphs for packing sequences with \(s_1 = 1\) and \(s_2 \geq 3\)
• About \(S\)-packing coloring of subcubic graphs
• On \(S\)-packing coloring of 2-saturated subcubic graphs
• On \(S\)-packing colourings of distance graphs \(D (1, t)\) and \(D (1, 2, t)\)

This page was built for publication: Packing \(( 1 , 1 , 2 , 2 )\)-coloring of some subcubic graphs

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