#chromatic number

[brightgreendandelions]

what is your chromatic number?

[probablymoons]

i woke up at 3am and then made this for an hour-and-a-half.. there wasn’t any system but i don’t think im missing any (lmk!). must use all 3 colors & same color can’t touch. darker color on the left just to keep track of duplicates

[matan-matika]

Graph Coloring

A graph is k-colorable if you can color the vertices with k colors and not have any vertex be the same color as any of its neighbors.

For example, a grid is 2-colorable.

A bipartite graph in general is 2-colorable, where one color is used for one side, and the other for the other side.

A complete graph, Kn, one where all n vertices are connected to every other vertex, is n-colorable.

Illustrations can be seen with the Kuratowski Graphs

If you noticed about that definition, a graph that is k-colorable is also k+1-colorable, because you can replace a vertex's color with one that is not used anywhere else.

You can also thing of a coloring as a function: color : V -> {color1, color2, color3, ... , colorn}

The smallest k such that a graph is k-colorable is called the chromatic number of that graph