MathDB

A. 848

Part of KoMaL A Problems 2022/2023

Problems(1)

Assigning vertices to faces in planar graph

Source: KoMaL A. 848

4/12/2023
Let GG be a planar graph, which is also bipartite. Is it always possible to assign a vertex to each face of the graph such that no two faces have the same vertex assigned to them?
Submitted by Dávid Matolcsi, Budapest
combinatoricsgraph theory