arXiv Analytics

Sign in

arXiv:1305.2467 [math.CO]AbstractReferencesReviewsResources

3-coloring triangle-free planar graphs with a precolored 8-cycle

Zdeněk Dvořák, Bernard Lidický

Published 2013-05-11Version 1

Let G be a planar triangle-free graph and let C be a cycle in G of length at most 8. We characterize all situations where a 3-coloring of C does not extend to a proper 3-coloring of the whole graph.

Comments: 20 pages, 5 figures
Categories: math.CO, cs.DM
Subjects: 05C15, 05C10, G.2.2
Related articles: Most relevant | Search more
arXiv:1402.5331 [math.CO] (Published 2014-02-21)
Fractional coloring of triangle-free planar graphs
arXiv:1505.07296 [math.CO] (Published 2015-05-27)
Fine structure of 4-critical triangle-free graphs II. Planar triangle-free graphs with two precolored 4-cycles
arXiv:2108.12669 [math.CO] (Published 2021-08-28)
Triangle-free planar graphs with at most $64^{n^{0.731}}$ 3-colorings

Links

Toolbox