Choosability with union separation of triangle-free planar graphs (Q2005734)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Choosability with union separation of triangle-free planar graphs
scientific article

    Statements

    Choosability with union separation of triangle-free planar graphs (English)
    0 references
    0 references
    0 references
    8 October 2020
    0 references
    This paper considers a variant of the list-chromatic number where restrictions are imposed on the lists. In this variation a \((k,k+s)\)-list assignment is such that the lists of adjacent vertices have a union of size at least \(k+s\). So \((k,k+s)\)-choosability is defined in the standard way, but with the above restriction: a proper colouring exists for any choice of lists of size \(k\) which satisfies the above. The authors consider this parameter in planar graphs which are locally sparse. In particular, for triangle-free planar graphs they show their \((3,7)\)-choosability. For those planar graphs of girth at least 5, they show \((2,7)\)-choosability. Their proofs use the discharging method, which has been used in the context of the four colour theorem.
    0 references
    choosability
    0 references
    planar graph
    0 references
    triangle
    0 references
    discharge
    0 references

    Identifiers