Restricted coloring problems on Graphs with few P 4 ’s

Cláudia Linhares-Sales (), Ana Maia (), Nicolas Martins () and Rudini Sampaio ()

Annals of Operations Research, 2014, vol. 217, issue 1, 385-397

Abstract: In this paper, we obtain linear time algorithms to determine the acyclic chromatic number, the star chromatic number, the non repetitive chromatic number and the clique chromatic number of P 4 -tidy graphs and (q, q − 4)-graphs, for every fixed q, which are the graphs such that every set with at most q vertices induces at most q − 4 distinct P 4 ’s. These classes include cographs and P 4 -sparse graphs. We also obtain a linear time algorithm to compute the harmonious chromatic number of connected P 4 -tidy graphs and connected (q, q − 4)-graphs. All these coloring problems are known to be NP-hard for general graphs. These algorithms are fixed parameter tractable on the parameter q(G), which is the minimum q such that G is a (q, q − 4)-graph. We also prove that every connected (q, q − 4)-graph with at least q vertices is 2-clique-colorable and that every acyclic coloring of a cograph is also nonrepetitive, generalizing the main result of Lyons ( 2011 ). Copyright Springer Science+Business Media New York 2014

Keywords: Fixed parameter algorithms; Acyclic coloring; Star coloring; Harmonious coloring; Nonrepetitive coloring; clique coloring; Thue chromatic number; Primeval decomposition; cographs; (q; q−4)-graphs (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-014-1537-2 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:217:y:2014:i:1:p:385-397:10.1007/s10479-014-1537-2

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-014-1537-2

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().