Punktfärbung

Punktfärbung, also known as point coloring, is a concept in discrete mathematics, particularly in graph theory. It refers to the assignment of colors to the vertices, or "points," of a graph. The primary constraint in a standard punktfärbung is that adjacent vertices, meaning those connected by an edge, must receive different colors.

The goal of a punktfärbung is often to find the minimum number of colors required to satisfy this condition for a given graph. This minimum number is called the chromatic number of the graph, denoted by $\chi(G)$. Graphs can have various chromatic numbers. For instance, a graph with no edges can be colored with a single color, while a complete graph $K_n$, where every pair of distinct vertices is connected by an edge, requires $n$ colors.

The problem of finding the chromatic number is computationally difficult, belonging to the class of NP-hard problems. However, there are known bounds and algorithms for specific types of graphs. For example, bipartite graphs, which are graphs whose vertices can be divided into two disjoint sets such that no two vertices within the same set are adjacent, always have a chromatic number of at most 2.

Punktfärbung has applications in various fields, including scheduling, resource allocation, and register allocation in computer science. For example, scheduling exams in a way that no two exams with common students overlap can be modeled as a punktfärbung problem.