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

Runrun Liu, Xujun Liu*, Martin Rolek, Gexin Yu

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)

Abstract

For a sequence of non-decreasing positive integers S=(s1,…,sk), a packing S-coloring is a partition of V(G) into sets V1,…,Vk such that for each 1≤i≤k the distance between any two distinct x,y∈Vi is at least si+1. The smallest k such that G has a packing (1,2,…,k)-coloring is called the packing chromatic number of G and is denoted by χp(G). For a graph G, let D(G) denote the graph obtained from G by subdividing every edge. The question whether χp(D(G))≤5 for all subcubic graphs G was first asked by Gastineau and Togni and later conjectured by Brešar, Klavžar, 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 max{[Formula presented]:H⊂G}. In this paper, we prove that subcubic graphs with mad(G)<[Formula presented] are packing (1,1,2,2)-colorable. As a corollary, the conjecture of Brešar et al holds for every subcubic graph G with mad(G)<[Formula presented].

Original languageEnglish
Pages (from-to)626-630
Number of pages5
JournalDiscrete Applied Mathematics
Volume283
DOIs
Publication statusPublished - 15 Sept 2020
Externally publishedYes

Keywords

  • Independent sets
  • Maximum average degree
  • Packing coloring
  • Subcubic graphs

Cite this