Title of article
Restricted coloring problems on graphs with few
Author/Authors
Campos، نويسنده , , V. and Linhares Sales، نويسنده , , C. and Maia، نويسنده , , K. and Martins، نويسنده , , N. and Sampaio، نويسنده , , R.، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2011
Pages
6
From page
57
To page
62
Abstract
In this paper, we obtain polynomial time algorithms to determine the acyclic chromatic number, the star chromatic number and the harmonious chromatic number of P 4 -tidy graphs and ( q , q − 4 )-graphs, for every fixed q. These classes include cographs, P 4 -sparse and P 4 -lite graphs. We also obtain a polynomial time algorithm to determine the Grundy number of ( q , q − 4 )-graphs. All these coloring problems are known to be NP-hard for general graphs.
Keywords
( q , q ? 4 )-graphs , P 4 -tidy graphs , polynomial time algorithms , Acyclic , STAR , harmonious and greedy colorings
Journal title
Electronic Notes in Discrete Mathematics
Serial Year
2011
Journal title
Electronic Notes in Discrete Mathematics
Record number
1455647
Link To Document