On Alon-Tarsi orientations of sparse graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909762946334720 |
|---|---|
| author | Cho, Eun-Kyung Choi, Ilkyoo Park, Boram Zhu, Xuding |
| author_facet | Cho, Eun-Kyung Choi, Ilkyoo Park, Boram Zhu, Xuding |
| contents | Assume $G$ is a graph, $(v_1,\ldots,v_k)$ is a sequence of distinct vertices of $G$, and $(a_1,\ldots,a_k)$ is an integer sequence with $a_i \in \{1,2\}$. We say $G$ is \emph{$(a_1,\ldots,a_k)$-list extendable} (respectively, \emph{$(a_1,\ldots,a_k)$-AT extendable}) with respect to $(v_1,\ldots,v_k)$ if $G$ is $f$-choosable (respectively, $f$-AT), where $f(v_i)=a_i $ for $i \in \{1,\ldots, k\}$, and $f(v)=3$ for $v \in V(G) \setminus \{v_1,\ldots, v_k\}$. Hutchinson proved that if $G$ is an outerplanar graph, then $G$ is $(2,2)$-list extendable with respect to $(x,y)$ for any vertices $x,y$. We strengthen this result and prove that if $G$ is a $K_4$-minor-free graph, then $G$ is $(2,2)$-AT extendable with respect to $(x,y)$ for any vertices $x,y$. Then we characterize all triples $(x,y,z)$ of a $K_4$-minor-free graph $G$ for which $G$ is $(2,2,2)$-AT extendable (as well as $(2,2,2)$-list extendable) with respect to $(x,y,z)$. We also characterize the pairs $(x,y)$ of a $K_4$-minor-free graph $G$ for which $G$ is $(2,1)$-AT extendable (as well as $(2,1)$-list extendable) with respect to $(x,y)$. Moreover, we characterize all triples $(x,y,z)$ of a 3-colorable graph $G$ with its maximum average degree less than $\frac{14}{5}$ for which $G$ is $(2,2,2)$-AT extendable with respect to $(x,y,z)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_00657 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On Alon-Tarsi orientations of sparse graphs Cho, Eun-Kyung Choi, Ilkyoo Park, Boram Zhu, Xuding Combinatorics Assume $G$ is a graph, $(v_1,\ldots,v_k)$ is a sequence of distinct vertices of $G$, and $(a_1,\ldots,a_k)$ is an integer sequence with $a_i \in \{1,2\}$. We say $G$ is \emph{$(a_1,\ldots,a_k)$-list extendable} (respectively, \emph{$(a_1,\ldots,a_k)$-AT extendable}) with respect to $(v_1,\ldots,v_k)$ if $G$ is $f$-choosable (respectively, $f$-AT), where $f(v_i)=a_i $ for $i \in \{1,\ldots, k\}$, and $f(v)=3$ for $v \in V(G) \setminus \{v_1,\ldots, v_k\}$. Hutchinson proved that if $G$ is an outerplanar graph, then $G$ is $(2,2)$-list extendable with respect to $(x,y)$ for any vertices $x,y$. We strengthen this result and prove that if $G$ is a $K_4$-minor-free graph, then $G$ is $(2,2)$-AT extendable with respect to $(x,y)$ for any vertices $x,y$. Then we characterize all triples $(x,y,z)$ of a $K_4$-minor-free graph $G$ for which $G$ is $(2,2,2)$-AT extendable (as well as $(2,2,2)$-list extendable) with respect to $(x,y,z)$. We also characterize the pairs $(x,y)$ of a $K_4$-minor-free graph $G$ for which $G$ is $(2,1)$-AT extendable (as well as $(2,1)$-list extendable) with respect to $(x,y)$. Moreover, we characterize all triples $(x,y,z)$ of a 3-colorable graph $G$ with its maximum average degree less than $\frac{14}{5}$ for which $G$ is $(2,2,2)$-AT extendable with respect to $(x,y,z)$. |
| title | On Alon-Tarsi orientations of sparse graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2509.00657 |