Some new bounds on \(T_{r}\)-choosability (Q2643324)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Some new bounds on \(T_{r}\)-choosability |
scientific article |
Statements
Some new bounds on \(T_{r}\)-choosability (English)
0 references
23 August 2007
0 references
Let \(G\) be a graph, \(T_r=\{0,1,\dots,r\}\) and let \(L\) be a function which assignes to every vertex \(v\) a list \(L(v)\) of admissible colours. Then \(L\)-\(T_r\)-colouring of \(G\) is a function \(c:V(G)\to\mathbb Z\), such that \(c(v)\in L(v)\) for all \(v\in V(G)\) and \(| c(v)-c(w)| \notin T_r\) for all \(vw\in E(G)\). If an \(L\)-\(T_r\)-colouring exists for every list assignment \(L\) such that \(| L(v)| =k\) for all \(v\in V(G)\), then \(G\) is said to be \(T_r\)-\(k\)-choosable, and the \(T_r\)-choosability \(T_r\)-ch\((G)\) of \(G\) is the smallest \(k\) for which \(G\) is \(T_r\)-\(k\)-choosable. The author presents the conjecture \(T_r -\text{ch}(G)\leq(2r-1)(\text{ch}(G)-1)+1\), where \(\text{ch}(G)\) is the choosability of \(G\). This conjecture is proved in the case \(\text{ch}(G)=2\), and also with the colouring number \(\text{col}(G)\) in place of \(\text{ch}(G)\).
0 references
\(T\)-colouring
0 references
list colouring
0 references
frequency assignment
0 references