Vertex colouring edge weightings: a logarithmic upper bound on weight-choosability

Kasper Szabo Lyngsie ; Liang Zhong

The electronic journal of combinatorics, Tome 28 (2021) no. 2

Résumé

A graph $G$ is said to be $(k,m)$-choosable if for any assignment of $k$-element lists $L_v \subset \mathbb{R}$ to the vertices $v \in V(G)$ and any assignment of $m$-element lists $L_e \subset \mathbb{R}$ to the edges $e \in E(G)$ there exists a total weighting $w: V(G) \cup E(G) \rightarrow \mathbb{R}$ of $G$ such that $w(v) \in L_v$ for any vertex $v \in V(G)$ and $w(e) \in L_e$ for any edge $e \in E(G)$ and furthermore, such that for any pair of adjacent vertices $u,v$, we have $w(u)+ \sum_{e \in E(u)}w(e) \neq w(v)+ \sum_{e \in E(v)}w(e)$, where $E(u)$ and $E(v)$ denote the edges incident to $u$ and $v$ respectively. In this paper we give an algorithmic proof showing that any graph $G$ without isolated edges is $(1, 2 \lceil \log_2(\Delta(G)) \rceil+1)$-choosable, where $\Delta(G)$ denotes the maximum degree in $G$.

Détail

DOI : 10.37236/6878

Classification : 05C15, 05C07
Mots-clés : \((k,m)\)-choosable graph, total weighting