A note on not-4-list colorable planar graphs (Q1640221)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 6888455
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | A note on not-4-list colorable planar graphs |
scientific article; zbMATH DE number 6888455 |
Statements
A note on not-4-list colorable planar graphs (English)
0 references
14 June 2018
0 references
Summary: The four color theorem states that every planar graph is properly 4-colorable. Moreover, it is well known that there are planar graphs that are non-4-list colorable. In this paper we investigate a problem combining proper colorings and list colorings. We ask whether the vertex set of every planar graph can be partitioned into two subsets where one subset induces a bipartite graph and the other subset induces a 2-list colorable graph. We answer this question in the negative strengthening the result on non-4-list colorable planar graphs.
0 references
list colouring
0 references
planar graph
0 references
0.8124291896820068
0 references
0.804508626461029
0 references
0.8021729588508606
0 references
0.7892258763313293
0 references
