2019/03/25 by Choi, Ilkyoo, Park, Boram · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1903.10133
A star k-coloring of a graph G is a proper (vertex) k-coloring of G such that the vertices on a path of length three receive at least three colors. Given a graph G, its star chromatic number, denoted χs(G), is the minimum integer k for which G admits a star k-coloring. Studying star coloring of sparse graphs is an active area of research, especially in terms of the maximum average degree of a graph; the maximum average degree, denoted mad(G), of a graph G is max\ (2|E(H)|)/(|V(H)|):H ⊂ G\. It is known that for a graph G, if mad(G)