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

DOI10.1016/J.DAM.2020.03.015zbMATH Open1442.05063OpenAlexW3011206457MaRDI 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)

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

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)

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$.

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

Cites Work

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

Cited In (15)

• \(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 edge-colorings of cubic graphs
• Packing chromatic number of subdivisions of cubic graphs
• On \(S\)-packing coloring of 2-saturated subcubic 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
• 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)