The Strong Fractional Choice Number and the Strong Fractional Paint Number of Graphs
SIAM Journal on Discrete Mathematics · 2022-12 · 36 (4) · 2585-2601
DOI: 10.1137/21m1434556 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 09.11.2022. Verfasst von Rongxing Xu und 1 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 29 Literaturangaben. Gefördert von: Fujian Provincial Department of Science and Technology, National Natural Science Foundation of China.
Abstract (Originalsprache)
This paper studies the strong fractional choice number $ch^s_f(G)$ and the strong fractional paint number $pt^s_f(G)$ of a graph $G$. We prove that these parameters of any finite graph are rational numbers. On the other hand, for any positive integers $p,q$ satisfying $2 \le \frac{2p}{2q+1} \leq \lfloor\frac{p}{q}\rfloor$, we construct a graph $G$ with $ch^s_f(G) = pt^s_f(G) = \frac{p}{q}$. The relationship between $pt^s_f(G)$ and $ch^s_f(G)$ is explored. We prove that the gap $pt^s_f(G)-ch^s_f(G)$ can be arbitrarily large. The strong fractional choice number of a family $\mathcal{G}$ of graphs is the supremum of the strong fractional choice numbers of graphs in $\mathcal{G}$. Let $\mathcal{P}$ denote the class of planar graphs and $\mathcal{P}_{k_1,\ldots, k_q}$ denote the class of planar graphs without $k_i$-cycles for $i=1,\ldots, q$. We prove that $3 + \frac{1}{2} \leq ch^s_f(\mathcal{P}_{ 4}) \leq 4$, $ch^s_f(\mathcal{P}_{ k})=4$ for $k \in \{5,6\}$, $3 +\frac{1}{12} \leq ch^s_f(\mathcal{P}_{ 4,5}) \leq 4$, and $ch^s_f(\mathcal{P}) \ge 4+\frac 13$. The last result improves the lower bound $4+\frac 29$ in [Zhu, J. Combin. Theory Ser. B, 122 (2017), pp. 794--799].
Förderung
- Fujian Provincial Department of Science and Technology
- National Natural Science Foundation of China
Zitieren
APA
Xu, R., & Zhu, X. (2022). The Strong Fractional Choice Number and the Strong Fractional Paint Number of Graphs. SIAM Journal on Discrete Mathematics, 36(4), 2585-2601. https://doi.org/10.1137/21m1434556
Vancouver
Xu R, Zhu X. The Strong Fractional Choice Number and the Strong Fractional Paint Number of Graphs. SIAM Journal on Discrete Mathematics. 2022;36(4):2585-2601. doi:10.1137/21m1434556
BibTeX
@article{Xu2022,
author = {Xu, Rongxing and Zhu, Xuding},
title = {The Strong Fractional Choice Number and the Strong Fractional Paint Number of Graphs},
journal = {SIAM Journal on Discrete Mathematics},
year = {2022},
volume = {36},
number = {4},
pages = {2585--2601},
doi = {10.1137/21m1434556}
}
EUVIMED