S-packing chromatic critical graphs

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

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.

• Jezik: Angleški jezik
• Ključne besede: packing coloring, S-packing coloring, S-packing critical graph, independence number, cycle graph
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Datum objave: 01.05.2026
• Leto izida: 2026
• Št. strani: Str. 77-85
• Številčenje: Vol. 385
• PID: 20.500.12556/RUL-178326
• UDK: 519.17
• ISSN pri članku: 0166-218X
• DOI: 10.1016/j.dam.2026.01.024
• COBISS.SI-ID: 265800451
• Datum objave v RUL: 23.01.2026

Gradivo je del revije

• Naslov: Discrete applied mathematics
• Skrajšan naslov: Discrete appl. math.
• Založnik: Elsevier
• ISSN: 0166-218X
• COBISS.SI-ID: 25342464

Licence

• Licenca: CC BY-NC 4.0, Creative Commons Priznanje avtorstva-Nekomercialno 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by-nc/4.0/deed.sl
• Opis: Licenca Creative Commons, ki prepoveduje komercialno uporabo, vendar uporabniki ne rabijo upravljati materialnih avtorskih pravic na izpeljanih delih z enako licenco.

Sekundarni jezik

• Jezik: Slovenski jezik
• Ključne besede: pakirno barvanje, S-pakirno barvanje, S-pakirno kritičen graf, neodvisnostno število, graf cikel