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 language | English |
|---|---|
| Journal | Journal of Combinatorial Theory. Series B |
| Volume | 158 |
| Pages (from-to) | 301-312 |
| ISSN | 0095-8956 |
| DOIs | |
| Publication status | Published - 2023 |
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
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver