Sub-exponentially many 3-colorings of triangle-free planar graphs
Asadi, Arash · Dvorak, Zdenek · Postle, Luke · Thomas, Robin
Original · EN
Thomassen conjectured that every triangle-free planar graph on n vertices has exponentially many 3-colorings, and proved that it has at least 2[n(1/12)/20000] distinct 3-colorings. We show that it has at least 2ˢqrt(n/362) distinct 3-colorings.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.