Coloring locally bipartite graphs on surfaces

Bojan Mohar, Paul D. Seymour

Research output: Contribution to journalArticlepeer-review

23 Scopus citations

Abstract

It is proved that there is a function f: ℕ → ℕ such that the following holds. Let G be a graph embedded in a surface of Euler genus g with all faces of even size and with edge-width ≥ f(g). Then (i) If every contractible 4-cycle of G is facial and there is a face of size > 4, then G is 3-colorable. (ii) If G is a quadrangulation, then G is not 3-colorable if and only if there exist disjoint surface separating cycles C1, ⋯, Cg such that, after cutting along C1, ⋯, Cg, we obtain a sphere with g holes and g Möbius strips, an odd number of which is nonbipartite. If embeddings of graphs are represented combinatorially by rotation systems and signatures [5], then the condition in (ii) is satisfied if and only if the geometric dual of G has an odd number of edges with negative signature.

Original languageEnglish (US)
Pages (from-to)301-310
Number of pages10
JournalJournal of Combinatorial Theory. Series B
Volume84
Issue number2
DOIs
StatePublished - Mar 2002

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Coloring locally bipartite graphs on surfaces'. Together they form a unique fingerprint.

Cite this