S-packing chromatic vertex-critical graphs

2020/01/25 by Holub, Přemysl, Jakovac, Marko, Klavžar, Sandi · 2 citations
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2001.09362

Abstract

For a non-decreasing sequence of positive integers S = (s₁,s₂,…), the \em S-packing chromatic number χ_S(G) of G is the smallest integer k such that the vertex set of G can be partitioned into sets X_i, i ∈ [k], where vertices in X_i are pairwise at distance greater than s_i. In this paper we introduce S-packing chromatic vertex-critical graphs, χ_S-critical for short, as the graphs in which χ_S(G-u)1. We also deal with k-χ_S-criticality of trees and caterpillars.

Cited by

• S-packing chromatic critical graphs
• Packing chromatic number of unitary Cayley graphs of \Bbb Z_n and algorithmic approaches to it

Related

• S-packing chromatic critical graphs
• A characterization of 4-χ_S-vertex-critical graphs for packing sequences with s₁ =1 and s₂≥ 3
• Graphs that are critical for the packing chromatic number
• A characterization of 4-χ_ρ-(vertex-)critical graphs
• Subdivision into i-packings and S-packing chromatic number of some lattices