Exponentially many 3-colorings of planar triangle-free graphs with no short separating cycles

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

The number of proper vertex-3-colorings of every triangle-free planar graph with n vertices and with no separating cycle of length 4 or 5 is at least 2n/17700000. On the other hand, for infinitely many n, there exists a triangle-free planar graph with separating cycles of length 4 and 5 whose number of proper vertex-3-colorings is <215n/log2⁡(n).

Original languageEnglish
JournalJournal of Combinatorial Theory. Series B
Number of pages15
ISSN0095-8956
DOIs
Publication statusAccepted/In press - 2021

Bibliographical note

Funding Information:
Supported by Independent Research Fund Denmark, 8021-002498 AlgoGraph.

Publisher Copyright:
© 2021 Elsevier Inc.

Keywords

  • 3-colorings
  • Planar graphs

Fingerprint Dive into the research topics of 'Exponentially many 3-colorings of planar triangle-free graphs with no short separating cycles'. Together they form a unique fingerprint.

Cite this