تقرير
Coloring near-quadrangulations of the cylinder and the torus
| العنوان: | Coloring near-quadrangulations of the cylinder and the torus |
|---|---|
| المؤلفون: | Dvořák, Zdeněk, Pekárek, Jakub |
| سنة النشر: | 2019 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics, Computer Science - Discrete Mathematics, 05C15 |
| الوصف: | Let G be a simple connected plane graph and let C_1 and C_2 be cycles in G bounding distinct faces f_1 and f_2. For a positive integer l, let r(l) denote the number of integers n such that -l<=n<=l, n is divisible by 3, and n has the same parity as l; in particular, r(4)=1. Let r_{f_1,f_2}(G) be the product of r(|f|) over all faces f of G distinct from f_1 and f_2, and let q(G)=1+sum_{f:|f|\neq 4} |f|, where the sum is over all faces f of G. We give an algorithm with time complexity O(r_{f_1,f_2}(G)q(G)|G|) which, given a 3-coloring psi of C_1 and C_2, either finds an extension of psi to a 3-coloring of G, or correctly decides no such extension exists. The algorithm is based on a min-max theorem for a variant of integer 2- commodity flows, and consequently in the negative case produces an obstruction to the existence of the extension. As a corollary, we show that every triangle-free graph drawn in the torus with edge-width at least 21 is 3-colorable. Comment: 34 pages, no figures |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/1909.12015 |
| رقم الأكسشن: | edsarx.1909.12015 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |