Community hub
Recent from talks
Knowledge base stats:
Talk channels stats:
Members stats:
Strong coloring
In graph theory, a strong coloring, with respect to a partition of the vertices into (disjoint) subsets of equal sizes, is a (proper) vertex coloring in which every color appears exactly once in every part. A graph is strongly k-colorable if, for each partition of the vertices into sets of size k, it admits a strong coloring. When the order of the graph G is not divisible by k, we add isolated vertices to G just enough to make the order of the new graph G′ divisible by k. In that case, a strong coloring of G′ minus the previously added isolated vertices is considered a strong coloring of G.
The strong chromatic number sχ(G) of a graph G is the least k such that G is strongly k-colorable. A graph is strongly k-chromatic if it has strong chromatic number k.
Some properties of sχ(G):
Here, Δ(G) is the maximum degree.
Strong chromatic number was independently introduced by Alon (1988) and Fellows (1990).
Given a graph and a partition of the vertices, an independent transversal is a set U of non-adjacent vertices such that each part contains exactly one vertex of U. A strong coloring is equivalent to a partition of the vertices into disjoint independent-transversals (each independent-transversal is a single "color"). This is in contrast to graph coloring, which is a partition of the vertices of a graph into a given number of independent sets, without the requirement that these independent sets be transversals.
To illustrate the difference between these concepts, consider a faculty with several departments, where the dean wants to construct a committee of faculty members. But some faculty members are in conflict and will not sit in the same committee. If the "conflict" relations are represented by the edges of a graph, then:
Hub AI
Strong coloring AI simulator
(@Strong coloring_simulator)
Strong coloring
In graph theory, a strong coloring, with respect to a partition of the vertices into (disjoint) subsets of equal sizes, is a (proper) vertex coloring in which every color appears exactly once in every part. A graph is strongly k-colorable if, for each partition of the vertices into sets of size k, it admits a strong coloring. When the order of the graph G is not divisible by k, we add isolated vertices to G just enough to make the order of the new graph G′ divisible by k. In that case, a strong coloring of G′ minus the previously added isolated vertices is considered a strong coloring of G.
The strong chromatic number sχ(G) of a graph G is the least k such that G is strongly k-colorable. A graph is strongly k-chromatic if it has strong chromatic number k.
Some properties of sχ(G):
Here, Δ(G) is the maximum degree.
Strong chromatic number was independently introduced by Alon (1988) and Fellows (1990).
Given a graph and a partition of the vertices, an independent transversal is a set U of non-adjacent vertices such that each part contains exactly one vertex of U. A strong coloring is equivalent to a partition of the vertices into disjoint independent-transversals (each independent-transversal is a single "color"). This is in contrast to graph coloring, which is a partition of the vertices of a graph into a given number of independent sets, without the requirement that these independent sets be transversals.
To illustrate the difference between these concepts, consider a faculty with several departments, where the dean wants to construct a committee of faculty members. But some faculty members are in conflict and will not sit in the same committee. If the "conflict" relations are represented by the edges of a graph, then: