University of Twente Student Theses

Login

Two-Face-Colourable maps

Helmink, Chendo (2024) Two-Face-Colourable maps.

[img] PDF
925kB
Abstract:We consider the following problem. We are given a plane graph G = (V, E). What is the smallest number of edges that we have to add to G to make it two-face-colourable? We show that a plane graph is two-face-colourable if and only if its inner vertices all have even degree. We present an algorithm that solves this problem in polynomial time.
Item Type:Essay (Bachelor)
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:31 mathematics
Programme:Applied Mathematics BSc (56965)
Link to this item:https://purl.utwente.nl/essays/102119
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page