| 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: | Plný text není přístupný. © Elsevier |
| Appears in Collections: | Články / Articles (NTIS) Články / Articles (KMA) OBD |
Files in This Item:
| File | Size | Format | |
|---|---|---|---|
| published.pdf | 761,04 kB | Adobe PDF | View/Open Request a copy |
Please use this identifier to cite or link to this item:
http://hdl.handle.net/11025/39874Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.