Discussiones Mathematicae Graph Theory 33(2) (2013)
373-385

doi: 10.7151/dmgt.1672

T. Karthick and C.R. Subramanian
Indian Statistical Institute, Chennai Centre |

**Keywords:** vertex coloring, star coloring, subcubic graphs

**2010 Mathematics Subject Classification:** 05C15, 05C85.

[1] | M.O. Albertson, G.G. Chappell, H.A. Kierstead, A. Kündgen and R. Ramamurthi, Coloring with no , Electron. J. Combin. 2-colored P's_{4} 11 (2004) #R26. |

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

[3] | M.I. Burstein, Every , Soobshcheniya Akademii Nauk Gruzinskoi SSR, 4-valent graph has an acyclic 5-coloring 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. |

[5] | T.F. Coleman and J.J. Moré, Estimation of sparse Hessian matrices and graph coloring problems, Math. Program. 28(3) (1984) 243--270, doi: 10.1007/BF02612334. |

[6] | G. Fertin, A. Raspaud and B. Reed, Star coloring of graphs, J. Graph Theory 47 (2004) 163--182, doi: 10.1002/jgt.20029. |

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

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

[9] | B. Grünbaum, Acyclic colorings of planar graphs, Israel J. Math. 14 (1973) 390--408, doi: 10.1007/BF02764716. |

[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 , Ars Math. Contemp. 5 are acyclically 7-colorable 4 (2011) 153--164. |

[12] | A. Lyons, Acyclic and star colorings of cographs, Discrete Appl. Math. 159 (2011) 1842--1850, doi: 10.1016/j.dam.2011.04.011. |

[13] | S. Skulrattankulchai, Acyclic colorings of subcubic graphs, Inform. Process. Lett. 92 (2004) 161--167, doi: 10.1016/j.ipl.2004.08.002. |

[14] | D.B. West, Introduction to Graph Theory, 2nd Edition (Prentice-Hall, Englewood Cliffs, New Jersey, 2000). |

Received 7 December 2011

Revised 23 May 2012

Accepted 23 May 2012