S-packing chromatic critical graphs

Boruzanli Ekinci, Gülnaz (author), Bujtás, Csilla (author), Gozüpek, Didem (author), Klavžar, Sandi (author)

For a non-decreasing sequence of positive integers $S=(s_1,s_2,\ldots)$, the $S$-packing chromatic number of a graph $G$ is denoted by $\chi_S(G)$. In this paper, $\chi_S$-critical graphs are introduced as the graphs $G$ such that $\chi_S(H) < \chi_S(G)$ for each proper subgraph $H$ of $G$. Several families of $\chi_S$-critical graphs are constructed, and $2$- and $3$-colorable $\chi_S$-critical graphs are presented for all packing sequences $S$, while $4$-colorable $\chi_S$-critical graphs are found for most of $S$. Cycles which are $\chi_S$-critical are characterized under different conditions. It is proved that for any graph $G$ and any edge $e \in E(G)$, the inequality $\chi_S(G - e) \ge \chi_S(G)/2$ holds. Moreover, in several important cases, this bound can be improved to $\chi_S(G - e) \ge (\chi_S(G)+1)/2$. The sharpness of the bounds is also discussed. Along the way an earlier result on $\chi_S$-vertex-critical graphs is supplemented.

• Language: English
• Keywords: packing coloring, S-packing coloring, S-packing critical graph, independence number, cycle graph
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FMF - Faculty of Mathematics and Physics
• Publication status: Published
• Publication version: Version of Record
• Publication date: 01.05.2026
• Year: 2026
• Number of pages: Str. 77-85
• Numbering: Vol. 385
• PID: 20.500.12556/RUL-178326
• UDC: 519.17
• ISSN on article: 0166-218X
• DOI: 10.1016/j.dam.2026.01.024
• COBISS.SI-ID: 265800451
• Publication date in RUL: 23.01.2026

Record is a part of a journal

• Title: Discrete applied mathematics
• Shortened title: Discrete appl. math.
• Publisher: Elsevier
• ISSN: 0166-218X
• COBISS.SI-ID: 25342464

Licences

• License: CC BY-NC 4.0, Creative Commons Attribution-NonCommercial 4.0 International
• Link: http://creativecommons.org/licenses/by-nc/4.0/
• Description: A creative commons license that bans commercial use, but the users don’t have to license their derivative works on the same terms.

Secondary language

• Language: Slovenian
• Keywords: pakirno barvanje, S-pakirno barvanje, S-pakirno kritičen graf, neodvisnostno število, graf cikel