DIKUL - logo
(UL)
  • Packing chromatic vertex-critical graphs [Elektronski vir]
    Klavžar, Sandi ; Rall, Douglas F.
    Pakirno kromatično število ▫$\chi_{\rho}(G)$▫ grafa ▫$G$▫ je najmanjše celo število ▫$k$▫, za katerega lahko množico vozlišč grafa ▫$G$▫ razdelimo v razrede ▫$V_i$▫, ▫$i\in [k]$▫, kjer so vozlišča iz ... ▫$V_i$▫ paroma na razdalji vsaj ▫$i+1$▫. Vozliščno-kritični grafi za pakirno kromatično število, na kratko ▫$\chi_{\rho}$▫-kritični grafi, so v članku vpeljani kot grafi ▫$G$▫, za katere velja ▫$\chi_{\rho}(G-x) < \chi_{\rho}(G)$▫ za vsako vozlišče ▫$x$▫ grafa ▫$G$▫. Če je ▫$\chi_{\rho}(G) = k$▫, potem je ▫$G$▫ ▫$k$▫-▫$\chi_{\rho}$▫-kritičen. Pokazano je, da če je ▫$G$▫ ▫$\chi_{\rho}$▫-kritičen, potem je lahko množica ▫$\{\chi_{\rho}(G) - \chi_{\rho}(G-x):\ x\in V(G)\}$▫ skoraj poljubna. Karakterizirani so ▫$3$▫-▫$\chi_{\rho}$▫-kritični grafi, medtem ko so ▫$4$▫-▫$\chi_{\rho}$▫-kritični grafi karakterizirani v primeru, ko vsebujejo cikel dolžine vsaj ▫$5$▫, ki ni kongruenten ▫$0$▫ po modulu ▫$4$▫. Dokazano je, da za vsako celo število ▫$k\ge 2$▫ obstaja ▫$k$▫-▫$\chi_{\rho}$▫-kritično drevo in da ▫$k$▫-▫$\chi_{\rho}$▫-kritična gosenica obstaja natanko tedaj, ko je ▫$k\le 7$▫. Obravnavani so tudi kartezični produkti. Med drugim je dokazano, da če sta ▫$G$▫ in ▫$H$▫ vozliščno-tranzitivna grafa in velja ▫${\rm diam}(G) + {\rm diam}(H) \le \chi_{\rho}(G)$▫, potem je tudi ▫$G\,\square\, H$▫ ▫$\chi_{\rho}$▫-kritičen.
    Vir: Discrete mathematics & theoretical computer science [Elektronski vir]. - ISSN 1365-8050 (Vol. 21, no. 3, Feb. 2019, art. 8, 18 str.)
    Vrsta gradiva - e-članek
    Leto - 2019
    Jezik - angleški
    COBISS.SI-ID - 18570841

    Povezava(-e):

    https://dmtcs.episciences.org/5186
    DOI

Vnos na polico