EUVIMEDEUVIMED entdecken
Crossref

Maximizing satisfied vertex requests in list coloring

Timothy Bennett, Michael C. Bowdoin, Haley Broadus, Daniel Hodgins, Jeffrey A. Mudrock, Adam K. Nusair, Gabriel Sharbel, Joshua Silverman

Congressus Numerantium · 30.06.2026 · 237 · 121-141

DOI: 10.61091/cn237-09 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Congressus Numerantium, online erschienen am 30.06.2026. Verfasst von Timothy Bennett und 7 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Suppose \(G\) is a graph and \(L\) is a list assignment for \(G\). A request of \(L\) is a function \(r\) with nonempty domain \(D\subseteq V(G)\) such that \(r(v) \in L(v)\) for each \(v \in D\). The triple \((G,L,r)\) is \(\epsilon\)-satisfiable if there exists a proper \(L\)-coloring \(f\) of \(G\) such that \(f(v) = r(v)\) for at least \(\epsilon|D|\) vertices in \(D\). We say \(G\) is \((k, \epsilon)\)-flexible if \((G,L',r')\) is \(\epsilon\)-satisfiable whenever \(L'\) is a \(k\)-assignment for \(G\) and \(r'\) is a request of \(L'\). It is known that a graph \(G\) is not \((k, \epsilon)\)-flexible for any \(k\) if and only if \(\epsilon > 1/ \rho(G)\) where \(\rho(G)\) is the Hall ratio of \(G\). The list flexibility number of a graph \(G\), denoted \(\chi_{\ell flex}(G)\), is the smallest \(k\) such that \(G\) is \((k,1/ \rho(G))\)-flexible. A fundamental open question on list flexibility numbers asks: Is there a graph with list flexibility number greater than its coloring number? In this paper, we show that the list flexibility number of any complete multipartite graph \(G\) is at most the coloring number of \(G\). We also initiate the study of list epsilon flexibility functions of complete bipartite graphs which was first suggested by Kaul, Mathew, Mudrock, and Pelsmajer in 2024. Specifically, we completely determine the list epsilon flexibility function of \(K_{m,n}\) when \(m \in \{1,2\}\) and establish some additional bounds for small \(m\). Our proofs reveal a connection to list coloring complete bipartite graphs with asymmetric list sizes which is a topic that was explored by Alon, Cambie, and Kang in 2021.

Zitieren

APA

Bennett, T., Bowdoin, M. C., Broadus, H., Hodgins, D., Mudrock, J. A., Nusair, A. K., Sharbel, G., & Silverman, J. (2026). Maximizing satisfied vertex requests in list coloring. Congressus Numerantium, 237, 121-141. https://doi.org/10.61091/cn237-09

Vancouver

Bennett T, Bowdoin MC, Broadus H, Hodgins D, Mudrock JA, Nusair AK, et al. Maximizing satisfied vertex requests in list coloring. Congressus Numerantium. 2026;237:121-141. doi:10.61091/cn237-09

BibTeX
@article{Bennett2026,
  author = {Bennett, Timothy and Bowdoin, Michael C. and Broadus, Haley and Hodgins, Daniel and Mudrock, Jeffrey A. and Nusair, Adam K. and Sharbel, Gabriel and Silverman, Joshua},
  title = {Maximizing satisfied vertex requests in list coloring},
  journal = {Congressus Numerantium},
  year = {2026},
  volume = {237},
  pages = {121--141},
  doi = {10.61091/cn237-09}
}
Kostenlos starten →