Maximization coloring problems on graphs with few
详细信息 查看全文
- 作者：Victor Campos ; Cl谩udia Linhares-Sales ; Rudini Sampaio ; Ana Karolinna Maia
- 关键词：Greedy coloring ; bb-coloring ; (q ; q&minus ; 4)(q ; q&minus ; 4)-graphs ; Primeval decomposition ; Fixed parameter tractable algorithms
- 刊名：Discrete Applied Mathematics
- 出版年：19 February, 2014
- 年：2014
- 卷：164
- 期：part_P2
- 页码：539-546
- 全文大小：433 K
文摘
Given a graph , a greedy coloring of is a proper coloring such that, for each two colors , every vertex of colored has a neighbor colored . The Grundy number is the maximum number of colors in a greedy coloring of . Zaker (2006) proved that determining the Grundy number is NP-hard even for complements of bipartite graphs. A -coloring of is a proper coloring such that every color class contains a vertex which is adjacent to at least one vertex in every other color class. The -chromatic number is the maximum number of colors in a -coloring of . Irving and Manlove (1999) proved that determining the -chromatic number is NP-hard. In this paper, we obtain polynomial time algorithms to determine the Grundy number and the -chromatic number of -graphs, for every fixed , which are the graphs such that every set of at most vertices induces at most distinct . These algorithms are fixed parameter tractable on the parameter , where is the minimum such that is a -graph.