In the

mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

field of

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 star coloring of a

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

is a (proper) vertex coloring in which every path on four vertices uses at least three distinct colors. Equivalently, in a star coloring, the

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 ...

s formed by the vertices of any two colors has connected components that are

star graph In graph theory, a star is the complete bipartite graph a tree (graph theory), tree with one internal node and leaves (but no internal nodes and leaves when ). Alternatively, some authors define to be the tree of order (graph theory), order ...

s. Star coloring has been introduced by . The star chromatic number of is the fewest colors needed to star color . One generalization of star coloring is the closely related concept of

acyclic coloring In graph theory, an acyclic coloring is a (proper) vertex coloring in which every 2-chromatic subgraph is acyclic. The acyclic chromatic number of a graph is the fewest colors needed in any acyclic coloring of . Acyclic coloring is often asso ...

, where it is required that every cycle uses at least three colors, so the two-color induced subgraphs are

forests A forest is an area of land dominated by trees. Hundreds of definitions of forest are used throughout the world, incorporating factors such as tree density, tree height, land use, legal standing, and ecological function. The United Nations' ...

. If we denote the acyclic chromatic number of a graph by , we have that , and in fact every star coloring of is an acyclic coloring. The star chromatic number has been proved to be bounded on every proper minor closed class by . This results was further generalized by to all low-tree-depth colorings (standard coloring and star coloring being low-tree-depth colorings with respective parameter 1 and 2).

Complexity

It was demonstrated by that 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 determine whether

\chi_s(G) \leq 3

, even when ''G'' is a graph that is both planar and

bipartite Bipartite may refer to: * 2 (number) * Bipartite (theology), a philosophical term describing the human duality of body and soul * Bipartite graph, in mathematics, a graph in which the vertices are partitioned into two sets and every edge has an en ...

. showed that finding an optimal star coloring is

NP-hard In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...

even when ''G'' is a bipartite graph.

References

*. *. *. *. * . * {{citation , first1 = Jaroslav , last1 = Nešetřil , authorlink1=Jaroslav Nešetřil , first2 = Patrice , last2 = Ossona de Mendez , author2-link = Patrice Ossona de Mendez , doi = 10.1016/j.ejc.2005.01.010 , mr = 2226435 , journal =

European Journal of Combinatorics European, or Europeans, or Europeneans, may refer to: In general * ''European'', an adjective referring to something of, from, or related to Europe ** Ethnic groups in Europe ** Demographics of Europe ** European cuisine European cuisine co ...

, volume = 27 , issue = 6 , pages = 1022–1041 , title = Tree depth, subgraph coloring and homomorphism bounds , year = 2006, doi-access = free.

External links

Star colorings and acyclic colorings (1973)
present at th
Research Experiences for Graduate Students (REGS)
at the University of Illinois, 2008. Graph coloring