Abstract | ||
---|---|---|
AbstractA star coloring of an undirected graph G is a proper vertex coloring of G i.e., no two adjacent vertices are assigned the same color such that no path on four vertices is 2-colored. The star chromatic number of G is the smallest integer k for which G admits a star coloring with k colors. In this paper, we prove that every subcubic graph is 6-star-colorable. Moreover, the upper bound 6 is best possible, based on the example constructed by Fertin, Raspaud, and Reed J Graph Theory 473 2004, 140-153. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1002/jgt.21636 | Periodicals |
Keywords | Field | DocType |
subcubic graph,vertex coloring,proper coloring,star-coloring | Discrete mathematics,Complete coloring,Topology,Edge coloring,Combinatorics,Fractional coloring,Graph power,Star coloring,List coloring,Greedy coloring,Mathematics,Graph coloring | Journal |
Volume | Issue | ISSN |
72 | 2 | 0364-9024 |
Citations | PageRank | References |
6 | 1.03 | 0 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Min Chen | 1 | 79 | 10.52 |
André Raspaud | 2 | 850 | 85.91 |
Weifan Wang | 3 | 868 | 89.92 |