2024/06/10 by Yiting Jiang, Jiang, Yiting, Huijuan Xu +5
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2406.06035
openalex publication_date 2024/06/10 · openalex created_date 2024/06/12 · openalex updated_date 2026/07/28
Assume G is a graph and k is a positive integer. Let f:V(G)→ ℕ be defined as f(v)=min\k,dG(v)\. If G is f-choosable, then we say G is degree-truncated k-choosable. Answering a question of Richter, it was proved in [Zhou,Zhu,Zhu, Degree-truncated choice number of graphs, arXiv:2308.15853] that there exists a 3-connected non-complete planar graph that is not degree-truncated 7-choosable, and every 3-connected non-complete planar graph is degree-truncated 16-choosable. This paper improves the bounds, and proves that there exists a 3-connected non-complete planar graph that is not degree-truncated 8-choosable, and that every 3-connected non-complete planar graph is degree-truncated 12-choosable.