S-packing chromatic critical graphs
Gülnaz Boruzanlı Ekinci, Csilla Bujtás, Didem Gözüpek, Sandi Klavžar · Discrete Applied Mathematics · 2026
For a non-decreasing sequence of positive integers S = ( s 1 , s 2 , … ) , the S -packing chromatic number of a graph G is denoted by χ S ( G ) . In this paper, χ S -critical graphs are introduced as the graphs G such that χ S ( H ) < χ S ( G ) for each proper subgraph H of G . Several families of χ S -critical graphs are constructed, and 2- and 3-colorable χ S -critical graphs are presented for all packing sequences S , while 4-colorable χ S -critical graphs are found for most of S . Cycles which are χ S -critical are characterized under different conditions. It is proved that for any graph G and any edge e ∈ E ( G ) , the inequality χ S ( G − e ) ≥ χ S ( G ) / 2 holds. Moreover, in several important cases, this bound can be improved to χ S ( G − e ) ≥ ( χ S ( G ) + 1 ) / 2 . The sharpness of the bounds is also discussed. Along the way an earlier result on χ S -vertex-critical graphs is supplemented.