1. Truncated-degree-choosability of planar graphs
- Author
-
Jiang, Yiting, Xu, Huijuan, Xu, Xinbo, and Zhu, Xuding
- Subjects
Mathematics - Combinatorics - Abstract
Assume $G$ is a graph and $k$ is a positive integer. Let $f:V(G)\to N$ be defined as $f(v)=\min\{k,d_G(v)\}$. If $G$ is $f$-choosable, then we say $G$ is $k$-truncated-degree-choosable. It was proved in [Zhou,Zhu,Zhu, Arc-weighted acyclic orientations and variations of degeneracy of graphs, arXiv:2308.15853] that there is a 3-connected non-complete planar graph that is not 7-truncated-degree-choosable, and every 3-connected non-complete planar graph is 16-truncated-degree-choosable. This paper improves the bounds, and proves that there is a 3-connected non-complete planar graph that is not 8-truncated-degree-choosable and every non-complete 3-connected planar graph is 12-truncated-degree-choosable., Comment: 17 pages, 1 figure
- Published
- 2024