Coloring
============

In graph theory, **vertex coloring** refers to the process of assigning colors to the vertices of a graph such that no two adjacent vertices share the same color. The smallest number of colors needed for a valid coloring is called the **chromatic number** of the graph.

A simple greedy algorithm for vertex coloring:

.. code-block:: python

   def greedy_color(graph, order):
       color = {}
       for v in order:  # default order
           # neighboring colors
           neighboring_colors = {color[u] for u in graph[v] if u in color}
           # first available color
           for c in itertools.count(0):
               if c not in neighboring_colors:
                   color[v] = c
                   break
       return color

.. image:: images/4coloring.png

Edge coloring and face coloring (for planar graphs) are also fundamental concepts. The **Four Color Theorem** states that any planar graph can be colored with at most four colors such that no adjacent regions share the same color.

Special cases:
- Bipartite graphs: Chromatic number = 2
- Trees: Chromatic number = 2
- Odd cycles: Chromatic number = 3

Example of checking bipartiteness:

.. code-block:: python

   def is_bipartite(graph):
       color = {}
       for v in graph:
           if v not in color:
               stack = [v]
               color[v] = 0
               while stack:
                   node = stack.pop()
                   for neighbor in graph[node]:
                       if neighbor in color:
                           if color[neighbor] == color[node]:
                               return False
                       else:
                           color[neighbor] = 1 - color[node]
                           stack.append(neighbor)
       return True  # graph is bipartite

Applications include scheduling, register allocation, and Sudoku puzzles.

Vertex Coloring
---------------
In vertex coloring, each vertex is assigned a color such that no two adjacent vertices share the same color.

.. _k-colorable:

k-colorable
~~~~~~~~~~~
If we can color the vertices of a graph using at most k colors, the graph is called **k-colorable**.

Proper k-Coloring
~~~~~~~~~~~~~~~~~~~~
If in vertex coloring we use k colors (such that for each color z, there exists at least one vertex colored with z), then the resulting coloring is called a proper k-coloring.

Chromatic Number
~~~~~~~~~
A graph is called **k-chromatic** if it is k-colorable but not (k-1)-colorable.  
The value **k** is referred to as the chromatic number of the graph, denoted by χ(G) = k.  
Essentially, the chromatic number of a graph indicates the minimum number of colors required to color the vertices of the graph.

Edge Coloring
-------------
If the edges of a graph can be colored with k colors, we say that the graph is **k-edge-colorable**.

Edge Chromatic Number
~~~~~~~~~~~~~~~~~~~~~
If a graph is edge-colorable with k colors but not edge-colorable with k-1 colors, we say the graph is k-edge-colorable. Here, k is considered the edge chromatic number of the graph and is denoted as χ′(G) = k.

.. Information about Coloring
---------------------------
Maps are colored in such a way that two neighboring countries do not share the same color.  
However, the question remained: what is the minimum number of colors required for such coloring?  
Francis Guthrie was the first to conjecture that every map can be colored with 4 colors.  
In 1976, Guthrie's conjecture was proven with computer assistance and became a theorem.