In the

mathematical Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

field of

graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

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

is a (proper)

vertex coloring In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a graph. The assignment is subject to certain constraints, such as that no two adjacent elements have the same color. Graph coloring i ...

in which every

path A path is a route for physical travel – see Trail. Path or PATH may also refer to: Physical paths of different types * Bicycle path * Bridle path, used by people on horseback * Course (navigation), the intended path of a vehicle * Desir ...

on four vertices uses at least three distinct colors. Equivalently, in a star coloring, the

induced subgraph In 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. Definition Formally, let G=(V,E) ...

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

star graph A star is a luminous spheroid of plasma (physics), plasma held together by Self-gravitation, self-gravity. The List of nearest stars and brown dwarfs, nearest star to Earth is the Sun. Many other stars are visible to the naked eye at night sk ...

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 ecosystem characterized by a dense community of 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 functio ...

. 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, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...

to determine whether

\chi_s(G) \leq 3

, even when ''G'' is a graph that is both planar and bipartite. showed that finding an optimal star coloring is

NP-hard In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...

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 The ''European Journal of Combinatorics'' is an international peer-reviewed scientific journal that specializes in combinatorics. The journal primarily publishes papers dealing with mathematical structures within combinatorics and/or establishing ...

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

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 NP-complete problems