TY - JOUR

T1 - Packing (1,1,2,4)-coloring of subcubic outerplanar graphs

AU - Kostochka, Alexandr

AU - Liu, Xujun

N1 - Funding Information:
Research of this author is supported in part by NSF, United States Grant DMS-1600592, NSF RTG, United States Grant DMS-1937241, Award RB17164 of the UIUC Campus Research Board, United States, and Grant 19-01-00682 of the Russian Foundation for Basic Research.The work was partially done while X. Liu was a Ph.D. student at Department of Mathematics, University of Illinois at Urbana?Champaign. Research of this author was supported by NSF grant Emerging Frontiers of Science of Information (A2209)1-482031-239010-191100.
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

UR - http://www.scopus.com/inward/citedby.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

VL - 302

SP - 8

EP - 15

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -