20.500.12556/RUL-178326 S-packing chromatic critical graphs 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. packing coloring S-packing coloring S-packing critical graph independence number cycle graph pakirno barvanje S-pakirno barvanje S-pakirno kritičen graf neodvisnostno število graf cikel true false true Angleški jezik Slovenski jezik Članek v reviji 2026-01-23 08:51:03 2026-01-23 08:51:07 2026-01-24 04:32:39 0000-00-00 00:00:00 2026 0 0 Str. 77-85 Vol. 385 May 2026 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 2026-05-01 519.17 0166-218X 10.1016/j.dam.2026.01.024 265800451 1-s2.0-S0166218X26000533-main.pdf 1-s2.0-S0166218X26000533-main.pdf 1 FF22BDC0A8C31D74458106D64AD164BA ce6067c4dc2c434f27f942e9330278854b66f065b74bc7e43409443bdd6065a2 df17e6d1-f830-11f0-a1ba-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=226067 https://www.sciencedirect.com/science/article/pii/S0166218X26000533 1 46f2513e-f830-11f0-a1ba-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=226064 Fakulteta za matematiko in fiziko 0 0 0