graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, a subfield of mathematics, a well-colored graph is an

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

for which

greedy coloring In the study of graph coloring problems in mathematics and computer science, a greedy coloring or sequential coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence a ...

uses the same number of colors regardless of the order in which colors are chosen for its vertices. That is, for these graphs, the

chromatic number In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...

(minimum number of colors) and

Grundy number In graph theory, the Grundy number or Grundy chromatic number of an undirected graph is the maximum number of colors that can be used by a greedy coloring strategy that considers the vertices of the graph in sequence and assigns each vertex its ...

(maximum number of greedily-chosen colors) are equal.

Examples

The well-colored graphs include the

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices ...

s and odd-length

cycle graph In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with vertices is called ...

s (the graphs that form the exceptional cases to Brooks' theorem) as well as the

complete bipartite graph In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17. Graph theory ...

s and complete multipartite graphs. The simplest example of a graph that is not well-colored is a four-vertex path. Coloring the vertices in path order uses two colors, the optimum for this graph. However, coloring the ends of the path first (using the same color for each end) causes the greedy coloring algorithm to use three colors for this graph. Because there exists a non-optimal vertex ordering, the path is not well-colored.

Complexity

A graph is well-colored if and only if does not have two vertex orderings for which the greedy coloring algorithm produces different numbers of colors. Therefore, recognizing non-well-colored graphs can be performed within the complexity class NP. On the other hand, a graph

G

has Grundy number

k

or more if and only if the graph obtained from

G

by adding a

(k-1)

-vertex clique is well-colored. Therefore, by a reduction from the Grundy number problem, it is

NP-complete In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryin ...

to test whether these two orderings exist. It follows that it is co-NP-complete to test whether a given graph is well-colored.

Related properties

A graph is hereditarily well-colored if every

induced subgraph In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset. Definit ...

is well-colored. The hereditarily well-colored graphs are exactly the

cograph In graph theory, a cograph, or complement-reducible graph, or ''P''4-free graph, is a graph that can be generated from the single-vertex graph ''K''1 by complementation and disjoint union. That is, the family of cographs is the smallest class of ...

s, the graphs that do not have a four-vertex path as an induced subgraph.

References

{{reflist, 30em, refs= {{citation , last1 = Christen , first1 = Claude A. , last2 = Selkow , first2 = Stanley M. , doi = 10.1016/0095-8956(79)90067-4 , issue = 1 , journal =

Journal of Combinatorial Theory The ''Journal of Combinatorial Theory'', Series A and Series B, are mathematical journals specializing in combinatorics and related areas. They are published by Elsevier. ''Series A'' is concerned primarily with structures, designs, and applicat ...

, mr = 539075 , pages = 49–59 , series = Series B , title = Some perfect coloring properties of graphs , volume = 27 , year = 1979, doi-access = free {{citation , last1 = Hansen , first1 = Pierre , last2 = Kuplinsky , first2 = Julio , doi = 10.1016/0012-365X(91)90313-Q , issue = 3 , journal = Discrete Mathematics , mr = 1139447 , pages = 199–212 , title = The smallest hard-to-color graph , volume = 96 , year = 1991, doi-access = free {{citation , last1 = Kosowski , first1 = Adrian , last2 = Manuszewski , first2 = Krzysztof , contribution = Classical coloring of graphs , doi = 10.1090/conm/352/06369 , mr = 2076987 , pages = 1–19 , publisher = American Mathematical Society , location = Providence, Rhode Island , series = Contemporary Mathematics , title = Graph Colorings , volume = 352 , year = 2004 {{citation , last = Zaker , first = Manouchehr , doi = 10.1016/j.disc.2005.06.044 , issue = 23 , journal =

Discrete Mathematics Discrete mathematics is the study of mathematical structures that can be considered "discrete" (in a way analogous to discrete variables, having a bijection with the set of natural numbers) rather than "continuous" (analogously to continu ...

, mr = 2273147 , pages = 3166–3173 , title = Results on the Grundy chromatic number of graphs , volume = 306 , year = 2006, doi-access = free Graph coloring Graph families