Title: S-packing chromatic vertex-critical graphs
Other Titles: Vrcholově-kritické grafy ve smyslu S-pakovacího barvení
Authors: Holub, Přemysl
Jakovac, Marko
Klavžar, Sandi
Citation: HOLUB, P., JAKOVAC, M., KLAVŽAR, S. S-packing chromatic vertex-critical graphs. Discrete applied mathematics, 2020, roč. 285, č. OCT 15 2020, s. 119-127. ISSN 0166-218X.
Issue Date: 2020
Publisher: Elsevier
Document type: článek
article
URI: 2-s2.0-85086367598
http://hdl.handle.net/11025/39874
ISSN: 0166-218X
Keywords: pakovací bavení;S-pakovací barvení;vrcholově-kritické grafy ve smyslu S-pakovacího barvení
Keywords in different language: packing colouring;S-packing colouring;S-packing vertex-critical graph
Abstract: V tomto článku představujeme vrcholově critické grafy ve smyslu S-pakovacího barvení, zkráceně chi_S-kritické, jako grafy G, v nichž chi_S(G-u)<chi_S(G) pro každý vrchol u v G. Ukážeme, že množina rozdílů hodnot chi_S(G) a chi_S(G-u) může být téměř libovolná. Je-li G chi_S-kritický a chi-S(G)=k, potom G nazýváme k-chi_S-kritický. Charakterizujeme 3-chi_S-kritické grafy a částečně charakterizujeme 4-chi_S-kritické grafy pro sekvence S, v nichž je první prvek roven 1. Rovněž se zabýváme k-chi_S-kritičností stromů a housenek.
Abstract in different language: In this paper we introduce S-packing chromatic vertex-critical graphs, chi_S-critical for short,as the graphs G in which chi_S(G-u)<chi_S(G) for every vertex u of G. We show that a set of differences between chi_S(G) and chi_S(G-u) can be almost arbitrary. If G is chi_S-critical and chi-S(G)=k, then G is called k-chi_S-critical. We characterize 3-chi_S-critical graphs and partially characterize 4-chi_S-critical graphs when the first element in S is 1. We also deal with k-chi_S-criticality of catterpillars and trees.
Rights: © Elsevier
Plný text není přístupný.
Appears in Collections:Články / Articles (NTIS)
Články / Articles (KMA)
OBD

Files in This Item:
File SizeFormat 
published.pdf761,04 kBAdobe PDFView/Open    Request a copy


Please use this identifier to cite or link to this item: http://hdl.handle.net/11025/39874

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

search
navigation
  1. DSpace at University of West Bohemia
  2. Publikační činnost / Publications
  3. OBD