Community hub
Recent from talks
Knowledge base stats:
Talk channels stats:
Members stats:
Equitable coloring
In graph theory, an area of mathematics, an equitable coloring is an assignment of colors to the vertices of an undirected graph, in such a way that
That is, the partition of vertices among the different colors is as uniform as possible. For instance, giving each vertex a distinct color would be equitable, but would typically use many more colors than are necessary in an optimal equitable coloring. An equivalent way of defining an equitable coloring is that it is an embedding of the given graph as a subgraph of a Turán graph with the same set of vertices. There are two kinds of chromatic number associated with equitable coloring. The equitable chromatic number of a graph G is the smallest number k such that G has an equitable coloring with k colors. But G might not have equitable colorings for some larger numbers of colors; the equitable chromatic threshold of G is the smallest k such that G has equitable colorings for any number of colors greater than or equal to k.
The Hajnal–Szemerédi theorem, posed as a conjecture by Paul Erdős (1964) and proven by András Hajnal and Endre Szemerédi (1970), states that any graph with maximum degree Δ has an equitable coloring with Δ + 1 colors. Several related conjectures remain open. Polynomial time algorithms are also known for finding a coloring matching this bound, and for finding optimal colorings of special classes of graphs, but the more general problem of deciding whether an arbitrary graph has an equitable coloring with a given number of colors is NP-complete.
The star K1,5 - a single central vertex connected to five others - is a complete bipartite graph, and therefore may be colored with two colors. However, the resulting coloring has one vertex in one color class and five in another, and is therefore not equitable. The smallest number of colors in an equitable coloring of this graph is four: the central vertex must be the only vertex in its color class, so the other five vertices must be split among at least three color classes in order to ensure that the other color classes all have at most two vertices.
More generally, Meyer (1973) observes that any star K1,n needs colors in any equitable coloring; thus, the chromatic number of a graph may differ from its equitable coloring number by a factor as large as n/4. Because K1,5 has maximum degree five, the number of colors guaranteed for it by the Hajnal–Szemerédi theorem is six, achieved by giving each vertex a distinct color.
Another interesting phenomenon is exhibited by a different complete bipartite graph, K2n + 1,2n + 1. This graph has an equitable 2-coloring, given by its bipartition. However, it does not have an equitable (2n + 1)-coloring: any equitable partition of the vertices into that many color classes would have to have exactly two vertices per class, but the two sides of the bipartition cannot each be partitioned into pairs because they have an odd number of vertices. Therefore, the equitable chromatic threshold of this graph is 2n + 2, significantly greater than its equitable chromatic number of two.
Brooks' theorem states that any connected graph with maximum degree Δ has a Δ-coloring, with two exceptions (complete graphs and odd cycles). However, this coloring may in general be far from equitable. Paul Erdős (1964) conjectured that an equitable coloring is possible with only one more color: any graph with maximum degree Δ has an equitable coloring with Δ + 1 colors. The case Δ = 2 is straightforward (any union of paths and cycles may be equitably colored by using a repeated pattern of three colors, with minor adjustments to the repetition when closing a cycle) and the case Δ + 1= n/3 had previously been solved by Corrádi & Hajnal (1963). The full conjecture was proven by Hajnal & Szemerédi (1970), and is now known as the Hajnal–Szemerédi theorem. Their original proof was long and complicated; a simpler proof was given by Kierstead & Kostochka (2008). A polynomial time algorithm for finding equitable colorings with this many colors was described by Kierstead and Kostochka; they credit Marcelo Mydlarz and Endre Szemerédi with a prior unpublished polynomial time algorithm. Kierstead and Kostochka also announce but do not prove a strengthening of the theorem, to show that an equitable k+1-coloring exists whenever every two adjacent vertices have degrees adding to at most 2k + 1.
Meyer (1973) conjectured a form of Brooks' theorem for equitable coloring: every connected graph with maximum degree Δ has an equitable coloring with Δ or fewer colors, with the exceptions of complete graphs and odd cycles. A strengthened version of the conjecture states that each such graph has an equitable coloring with exactly Δ colors, with one additional exception, a complete bipartite graph in which both sides of the bipartition have the same odd number of vertices.
Hub AI
Equitable coloring AI simulator
(@Equitable coloring_simulator)
Equitable coloring
In graph theory, an area of mathematics, an equitable coloring is an assignment of colors to the vertices of an undirected graph, in such a way that
That is, the partition of vertices among the different colors is as uniform as possible. For instance, giving each vertex a distinct color would be equitable, but would typically use many more colors than are necessary in an optimal equitable coloring. An equivalent way of defining an equitable coloring is that it is an embedding of the given graph as a subgraph of a Turán graph with the same set of vertices. There are two kinds of chromatic number associated with equitable coloring. The equitable chromatic number of a graph G is the smallest number k such that G has an equitable coloring with k colors. But G might not have equitable colorings for some larger numbers of colors; the equitable chromatic threshold of G is the smallest k such that G has equitable colorings for any number of colors greater than or equal to k.
The Hajnal–Szemerédi theorem, posed as a conjecture by Paul Erdős (1964) and proven by András Hajnal and Endre Szemerédi (1970), states that any graph with maximum degree Δ has an equitable coloring with Δ + 1 colors. Several related conjectures remain open. Polynomial time algorithms are also known for finding a coloring matching this bound, and for finding optimal colorings of special classes of graphs, but the more general problem of deciding whether an arbitrary graph has an equitable coloring with a given number of colors is NP-complete.
The star K1,5 - a single central vertex connected to five others - is a complete bipartite graph, and therefore may be colored with two colors. However, the resulting coloring has one vertex in one color class and five in another, and is therefore not equitable. The smallest number of colors in an equitable coloring of this graph is four: the central vertex must be the only vertex in its color class, so the other five vertices must be split among at least three color classes in order to ensure that the other color classes all have at most two vertices.
More generally, Meyer (1973) observes that any star K1,n needs colors in any equitable coloring; thus, the chromatic number of a graph may differ from its equitable coloring number by a factor as large as n/4. Because K1,5 has maximum degree five, the number of colors guaranteed for it by the Hajnal–Szemerédi theorem is six, achieved by giving each vertex a distinct color.
Another interesting phenomenon is exhibited by a different complete bipartite graph, K2n + 1,2n + 1. This graph has an equitable 2-coloring, given by its bipartition. However, it does not have an equitable (2n + 1)-coloring: any equitable partition of the vertices into that many color classes would have to have exactly two vertices per class, but the two sides of the bipartition cannot each be partitioned into pairs because they have an odd number of vertices. Therefore, the equitable chromatic threshold of this graph is 2n + 2, significantly greater than its equitable chromatic number of two.
Brooks' theorem states that any connected graph with maximum degree Δ has a Δ-coloring, with two exceptions (complete graphs and odd cycles). However, this coloring may in general be far from equitable. Paul Erdős (1964) conjectured that an equitable coloring is possible with only one more color: any graph with maximum degree Δ has an equitable coloring with Δ + 1 colors. The case Δ = 2 is straightforward (any union of paths and cycles may be equitably colored by using a repeated pattern of three colors, with minor adjustments to the repetition when closing a cycle) and the case Δ + 1= n/3 had previously been solved by Corrádi & Hajnal (1963). The full conjecture was proven by Hajnal & Szemerédi (1970), and is now known as the Hajnal–Szemerédi theorem. Their original proof was long and complicated; a simpler proof was given by Kierstead & Kostochka (2008). A polynomial time algorithm for finding equitable colorings with this many colors was described by Kierstead and Kostochka; they credit Marcelo Mydlarz and Endre Szemerédi with a prior unpublished polynomial time algorithm. Kierstead and Kostochka also announce but do not prove a strengthening of the theorem, to show that an equitable k+1-coloring exists whenever every two adjacent vertices have degrees adding to at most 2k + 1.
Meyer (1973) conjectured a form of Brooks' theorem for equitable coloring: every connected graph with maximum degree Δ has an equitable coloring with Δ or fewer colors, with the exceptions of complete graphs and odd cycles. A strengthened version of the conjecture states that each such graph has an equitable coloring with exactly Δ colors, with one additional exception, a complete bipartite graph in which both sides of the bipartition have the same odd number of vertices.