Discover published sets by community

The chromatic number of a graph is the smallest number of colors needed to color the vertices of the graph so that no two adjacent vertices share the same color.

A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex from one set to a vertex from the other set. The chromatic number of a bipartite graph is 2, provided the graph contains at least one edge.

In graph theory, a vertex (or node) is a fundamental unit out of which graphs are formed, representing an atomic unit of data, entity or a point where lines intersect.

A greedy coloring algorithm is an iterative procedure that assigns colors to vertices of a graph in a sequence, such that the current vertex is assigned the smallest available color that has not been used by its neighbors.

An edge in a graph is a line or arc that connects a pair of vertices. Edges represent the relationship or connection between vertices.

Two vertices in a graph are adjacent if they are connected by an edge. In the context of graph coloring, adjacent vertices must be assigned different colors.

A planar graph is a graph that can be drawn on a plane without any of its edges crossing. Planar graphs obey the Four Color Theorem for vertex coloring.

A coloring theorem is a statement that gives conditions under which certain kinds of graph coloring are possible. A well-known example is the Four Color Theorem, which states that any planar graph can be colored with no more than four colors such that no adjacent vertices have the same color.

A complete graph is a simple graph in which every pair of distinct vertices is connected by a unique edge. The chromatic number of a complete graph with $n$ vertices is $n$.