Description

A conflict-free k-coloring of a graph involves giving some of the vertices one of k different colours so that for each vertex v and each of v's neighbours, there is a colour that is given to exactly one vertex. Such colorings are extensively researched in graph theory and have applications in wireless networking, robotics, and geometry. Here, we look at the naturally occurring issue of the least k for which conflict-free k-colorings exist, the conflict-free chromatic number CF(G). We present outcomes for both closed neighbourhoods N v], where a vertex v belongs to its neighbourhood, and open neighbourhoods N(v), where a vertex v does not belong to its neighbourhood.

Vertex-set V and edge-set E are both present in a hypergraph H. In a hypergraph, an edge may have more vertices than two, whereas in a graph, an edge can only contain a maximum of two vertices. Each vertex of a V is given a different colour when it is coloured.

If each edge has at least one vertex with a distinct colour, the colouring is conflict-free. The two vertices next to each edge should have a distinct colour if H is a graph, which makes this requirement the norm for a valid colouring of a graph.

Conflict-free colorings are necessary for RFID protocols, cellular antenna frequency band assignment, and sensor network battery consumption issues.