On the Grundy Number of a Graph

被引：0

作者：

Havet, Frederic ^{[1
]}

Sampaio, Leonardo ^{[1
]}

机构：

[1] UNSA, CNRS, I3S, Projet Mascotte, F-06902 Sophia Antipolis, France

来源：

PARAMETERIZED AND EXACT COMPUTATION | 2010年 / 6478卷

关键词：

Colouring; Online Colouring; Greedy Colouring; NP-completeness; Fixed Parameter Complexity;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The Grundy number of a graph G, denoted by Gamma(G), is the largest k such that G has a greedy k-colouring, that is a colouring with k colours obtained by applying the greedy algorithm according to some ordering of the vertices of G. Trivially Gamma(G) <= Delta(G) + 1. In this paper, we show that deciding if Gamma(G) <= Delta(G) is NP-complete. We then show that deciding if Gamma(G) >= vertical bar V(G)vertical bar - k is fixed parameter tractable with respect to the parameter k.

引用

页码：170 / 179

页数：10

共 50 条

[31] The complexity of the proper orientation number [J].

Ahadi, A. ;

Dehghan, A. .

INFORMATION PROCESSING LETTERS, 2013, 113 (19-21) :799-803

[32] Augmenting the Rigidity of a Graph in R2 [J].

A. García ;

J. Tejel .

Algorithmica, 2011, 59 :145-168

[33] Complexity of Finding Graph Roots with Girth Conditions [J].

Babak Farzad ;

Lap Chi Lau ;

Van Bang Le ;

Nguyen Ngoc Tuy .

Algorithmica, 2012, 62 :38-53

[34] Complexity of Fall Coloring for Restricted Graph Classes [J].

Lauri, Juho ;

Mitillos, Christodoulos .

COMBINATORIAL ALGORITHMS, IWOCA 2019, 2019, 11638 :352-364

[35] Vertex elimination orderings for hereditary graph classes [J].

Aboulker, Pierre ;

Charbit, Pierre ;

Trotignon, Nicolas ;

Vuskovic, Kristina .

DISCRETE MATHEMATICS, 2015, 338 (05) :825-834

[36] Complexity of Finding Graph Roots with Girth Conditions [J].

Farzad, Babak ;

Lau, Lap Chi ;

Van Bang Le ;

Nguyen Ngoc Tuy .

ALGORITHMICA, 2012, 62 (1-2) :38-53

[37] The complexity of power indexes with graph restricted coalitions [J].

Benati, Stefano ;

Rizzi, Romeo ;

Tovey, Craig .

MATHEMATICAL SOCIAL SCIENCES, 2015, 76 :53-63

[38] On k-Vertex-Edge Domination of Graph [J].

Bhattacharya, Debojyoti ;

Paul, Subhabrata .

BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY, 2024, 47 (02)

[39] Complexity of Fall Coloring for Restricted Graph Classes [J].

Lauri, Juho ;

Mitillos, Christodoulos .

THEORY OF COMPUTING SYSTEMS, 2020, 64 (07) :1183-1196

[40] On the complement graph and defensive k-alliances [J].

Sigarreta, J. M. ;

Bermudo, S. ;

Fernau, H. .

DISCRETE APPLIED MATHEMATICS, 2009, 157 (08) :1687-1695

← 1 2 3 4 5 →