Choosability of graphs with infinite sets of forbidden differences (Q2462372)

From MaRDI portal
Revision as of 12:44, 27 June 2024 by ReferenceBot (talk | contribs) (‎Changed an Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
Choosability of graphs with infinite sets of forbidden differences
scientific article

    Statements

    Choosability of graphs with infinite sets of forbidden differences (English)
    0 references
    0 references
    30 November 2007
    0 references
    Suppose \(G\) is a (finite) graph, \(T\) is a set of non-negative integers, and for each vertex \(v\) of \(G\) we are given a set \(L(v)\) of integers. \(G\) is \(T\)-colorable from the list-assigment \(L\) if it is possible to choose for each vertex a color \(c(v)\in L(v)\) in such a way that \(\left| c(v)-c(w)\right| \not\in T\) whenever \(v\) and \(w\) are neighbors. If \(G\) is \(T\)-colorable from every \(L\) that has \(\left| L(v)\right| \geq k\) for every \(v\), then \(G\) is \(T\)-\(k\)-choosable; the \(T\)-choice number of \(G\) is the smallest integer \(k\) such that \(G\) is \(T\)-\(k\)-choosable, if any such \(k\) exists. If \(T\) is infinite then it might seem possible that some nonempty graphs have finite \(T\)-choice numbers, and other graphs do not. The author proves that this cannot happen: if \(K_{2}\) is \(T\)-\(k\)-choosable then a graph \(G\) of maximum degree \(\Delta \) is \(T\)-\(\ell\)-choosable for every \(\ell \geq (k-1)(4e\Delta )^{k}\), and also for every \(\ell \geq ((k-1)+3)k^{\Delta }\). Noting that the first of these lower bounds is polynomial in \(\Delta \) and the second is polynomial in \(k\), he asks whether or not it is possible to find a bound that is polynomial in both \(\Delta \) and \(k\).
    0 references
    graph coloring
    0 references
    list coloring
    0 references
    \(T\)-coloring
    0 references

    Identifiers