Coloring near-quadrangulations of the cylinder and the torus. (March 2021)

• Record Type: Journal Article
• Authors: Dvořák, Zdeněk; Pekárek, Jakub
• Is Part Of: European journal of combinatorics. Volume 93(2021)
• Publication Date: 2021-03
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2020.103258
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: 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 ℓ, let r ( ℓ ) denote the number of integers n such that − ℓ ≤ n ≤ ℓ, n is divisible by 3, and n has the same parity as ℓ ; in particular, r ( 4 ) = 1 . Let r f 1, f 2 ( G ) = ∏ f r ( | f | ), where the product is over the faces f of G distinct from f 1 and f 2, and let q ( G ) = 1 + ∑ f : | f | ≠ 4 | f |, where the sum is over all faces f of G (of length other than four). We give an algorithm with time complexity O ( r f 1, f 2 ( G ) q ( G ) | G | ) which, given a 3-coloring ψ of C 1 ∪ C 2, either finds an extension of ψ 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.