# Star Coloring of Subcubic Graphs

Discussiones Mathematicae Graph Theory (2013)

- Volume: 33, Issue: 2, page 373-385
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topT. Karthick, and C.R. Subramanian. "Star Coloring of Subcubic Graphs." Discussiones Mathematicae Graph Theory 33.2 (2013): 373-385. <http://eudml.org/doc/268043>.

@article{T2013,

abstract = {A star coloring of an undirected graph G is a coloring of the vertices of G such that (i) no two adjacent vertices receive the same color, and (ii) no path on 4 vertices is bi-colored. The star chromatic number of G, χs(G), is the minimum number of colors needed to star color G. In this paper, we show that if a graph G is either non-regular subcubic or cubic with girth at least 6, then χs(G) ≤ 6, and the bound can be realized in linear time.},

author = {T. Karthick, C.R. Subramanian},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {vertex coloring; star coloring; subcubic graphs},

language = {eng},

number = {2},

pages = {373-385},

title = {Star Coloring of Subcubic Graphs},

url = {http://eudml.org/doc/268043},

volume = {33},

year = {2013},

}

TY - JOUR

AU - T. Karthick

AU - C.R. Subramanian

TI - Star Coloring of Subcubic Graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2013

VL - 33

IS - 2

SP - 373

EP - 385

AB - A star coloring of an undirected graph G is a coloring of the vertices of G such that (i) no two adjacent vertices receive the same color, and (ii) no path on 4 vertices is bi-colored. The star chromatic number of G, χs(G), is the minimum number of colors needed to star color G. In this paper, we show that if a graph G is either non-regular subcubic or cubic with girth at least 6, then χs(G) ≤ 6, and the bound can be realized in linear time.

LA - eng

KW - vertex coloring; star coloring; subcubic graphs

UR - http://eudml.org/doc/268043

ER -

## References

top- [1] M.O. Albertson, G.G. Chappell, H.A. Kierstead, A. Kündgen and R. Ramamurthi, Coloring with no 2-colored P4’s, Electron. J. Combin. 11 (2004) #R26. Zbl1053.05045
- [2] N.R. Aravind and C.R. Subramanian, Bounds on vertex colorings with restrictions on the union of color classes, J. Graph Theory 66 (2011) 213-234. doi:10.1002/jgt.20501[Crossref][WoS] Zbl1228.05147
- [3] M.I. Burstein, Every 4-valent graph has an acyclic 5-coloring, Soobshcheniya Akademii Nauk Gruzinskoi SSR, 93 (1979) 21-24 (in Russian).
- [4] T.F. Coleman and J.Y. Cai, The cyclic coloring problem an estimation of sparse Hessian matrices, SIAM Journal of Algebraic and Discrete Methods 7 (1986) 221-235. doi:10.1137/0607026[Crossref]
- [5] T.F. Coleman and J.J. Mor´e, Estimation of sparse Hessian matrices and graph coloring problems, Math. Program. 28(3) (1984) 243-270. doi:10.1007/BF02612334[Crossref]
- [6] G. Fertin, A. Raspaud and B. Reed, Star coloring of graphs, J. Graph Theory 47 (2004) 163-182. doi:10.1002/jgt.20029[Crossref] Zbl1055.05051
- [7] A.H. Gebremedhin, F. Manne and A. Pothen, What color is your Jacobian? Graph coloring for computing derivatives, SIAM Rev. 47 (2005) 629-705. doi:10.1137/S0036144504444711[Crossref] Zbl1076.05034
- [8] A.H. Gebremedhin, A. Tarafdar, F. Manne and A. Pothen, New acyclic and star coloring algorithms with applications to computing Hessians, SIAM J. Sci. Comput. 29 (2007) 1042-1072. doi:10.1137/050639879[WoS][Crossref]
- [9] B. Grünbaum, Acyclic colorings of planar graphs, Israel J. Math. 14 (1973) 390-408. doi:10.1007/BF02764716[Crossref] Zbl0265.05103
- [10] T.R. Jensen and B. Toft, Graph Coloring Problems (Wiley-Interscience, New York, 1995).
- [11] A.V. Kostochka and C. Stocker, Graphs with maximum degree 5 are acyclically 7- colorable, Ars Math. Contemp. 4 (2011) 153-164. Zbl1236.05083
- [12] A. Lyons, Acyclic and star colorings of cographs, Discrete Appl. Math. 159 (2011) 1842-1850. doi:10.1016/j.dam.2011.04.011[Crossref][WoS] Zbl1228.05156
- [13] S. Skulrattankulchai, Acyclic colorings of subcubic graphs, Inform. Process. Lett. 92 (2004) 161-167. doi:10.1016/j.ipl.2004.08.002[Crossref]
- [14] D.B. West, Introduction to Graph Theory, 2nd Edition (Prentice-Hall, Englewood Cliffs, New Jersey, 2000).