An Alon-Tarsi Style Theorem for Additive Colorings
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917720379883520 |
|---|---|
| author | Gossett, Ian |
| author_facet | Gossett, Ian |
| contents | We first give an alternative proof of the Alon-Tarsi list coloring theorem. We use the ideas from this proof to obtain the following result, which is an additive coloring analog of the Alon-Tarsi Theorem: Let $G$ be a graph and let $D$ be an orientation of $G$. We introduce a new digraph $\mathcal{W}(D)$, such that if the out-degree in $D$ of each vertex $v$ is $d_v$, and if the number of Eulerian subdigraphs of $\mathcal{W}(D)$ with an even number of edges differs from the number of Eulerian subdigraphs of $\mathcal{W}(D)$ with an odd number of edges, then for any assignment of lists $L(v)$ of $d_v+1$ positive integers to the vertices of $G$, there is an additive coloring of $G$ assigning to each vertex $v$ an element from $L(v)$. As an application, we prove an additive list coloring result for tripartite graphs $G$ such that one of the color classes of $G$ contains only vertices whose neighborhoods are complete. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_02190 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | An Alon-Tarsi Style Theorem for Additive Colorings Gossett, Ian Combinatorics We first give an alternative proof of the Alon-Tarsi list coloring theorem. We use the ideas from this proof to obtain the following result, which is an additive coloring analog of the Alon-Tarsi Theorem: Let $G$ be a graph and let $D$ be an orientation of $G$. We introduce a new digraph $\mathcal{W}(D)$, such that if the out-degree in $D$ of each vertex $v$ is $d_v$, and if the number of Eulerian subdigraphs of $\mathcal{W}(D)$ with an even number of edges differs from the number of Eulerian subdigraphs of $\mathcal{W}(D)$ with an odd number of edges, then for any assignment of lists $L(v)$ of $d_v+1$ positive integers to the vertices of $G$, there is an additive coloring of $G$ assigning to each vertex $v$ an element from $L(v)$. As an application, we prove an additive list coloring result for tripartite graphs $G$ such that one of the color classes of $G$ contains only vertices whose neighborhoods are complete. |
| title | An Alon-Tarsi Style Theorem for Additive Colorings |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2302.02190 |