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
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