TY - JOUR
T1 - Packing (1,1,2,4)-coloring of subcubic outerplanar graphs
AU - Kostochka, Alexandr
AU - Liu, Xujun
N1 - Publisher Copyright:
© 2021 Elsevier B.V.
PY - 2021/10/30
Y1 - 2021/10/30
N2 - For 1≤s1≤s2≤…≤sk and a graph G, a packing (s1,s2,…,sk)-coloring of G is a partition of V(G) into sets V1,V2,…,Vk such that, for each 1≤i≤k the distance between any two distinct x,y∈Vi is at least si+1. The packing chromatic number, χp(G), of a graph G is the smallest k such that G has a packing (1,2,…,k)-coloring. It is known that there are trees of maximum degree 4 and subcubic graphs G with arbitrarily large χp(G). Recently, there was a series of papers on packing (s1,s2,…,sk)-colorings of subcubic graphs in various classes. We show that every 2-connected subcubic outerplanar graph has a packing (1,1,2)-coloring and every subcubic outerplanar graph is packing (1,1,2,4)-colorable. Our results are sharp in the sense that there are 2-connected subcubic outerplanar graphs that are not packing (1,1,3)-colorable and there are subcubic outerplanar graphs that are not packing (1,1,2,5)-colorable. We also show subcubic outerplanar graphs that are not packing (1,2,2,4)-colorable and not packing (1,1,3,4)-colorable.
AB - For 1≤s1≤s2≤…≤sk and a graph G, a packing (s1,s2,…,sk)-coloring of G is a partition of V(G) into sets V1,V2,…,Vk such that, for each 1≤i≤k the distance between any two distinct x,y∈Vi is at least si+1. The packing chromatic number, χp(G), of a graph G is the smallest k such that G has a packing (1,2,…,k)-coloring. It is known that there are trees of maximum degree 4 and subcubic graphs G with arbitrarily large χp(G). Recently, there was a series of papers on packing (s1,s2,…,sk)-colorings of subcubic graphs in various classes. We show that every 2-connected subcubic outerplanar graph has a packing (1,1,2)-coloring and every subcubic outerplanar graph is packing (1,1,2,4)-colorable. Our results are sharp in the sense that there are 2-connected subcubic outerplanar graphs that are not packing (1,1,3)-colorable and there are subcubic outerplanar graphs that are not packing (1,1,2,5)-colorable. We also show subcubic outerplanar graphs that are not packing (1,2,2,4)-colorable and not packing (1,1,3,4)-colorable.
KW - Cubic graphs
KW - Independent sets
KW - Packing coloring
UR - http://www.scopus.com/inward/record.url?scp=85107722387&partnerID=8YFLogxK
U2 - 10.1016/j.dam.2021.05.031
DO - 10.1016/j.dam.2021.05.031
M3 - Article
AN - SCOPUS:85107722387
SN - 0166-218X
VL - 302
SP - 8
EP - 15
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
ER -