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 条
[1]   On the Grundy and b-Chromatic Numbers of a Graph [J].
Frédéric Havet ;
Leonardo Sampaio .
Algorithmica, 2013, 65 :885-899
[2]   On the Grundy and b-Chromatic Numbers of a Graph [J].
Havet, Frederic ;
Sampaio, Leonardo .
ALGORITHMICA, 2013, 65 (04) :885-899
[3]   The graph tessellation cover number: Chromatic bounds, efficient algorithms and hardness [J].
Abreu, A. ;
Cunha, L. ;
de Figueiredo, C. ;
Kowada, L. ;
Marquezino, F. ;
Posner, D. ;
Portugal, R. .
THEORETICAL COMPUTER SCIENCE, 2020, 801 :175-191
[4]   The number of recombination events in a sample history: Conflict graph and lower bounds [J].
Bafna, V ;
Bansal, V .
IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS, 2004, 1 (02) :78-90
[5]   The Graph Tessellation Cover Number: Extremal Bounds, Efficient Algorithms and Hardness [J].
Abreu, Alexandre ;
Cunha, Luis ;
Fernandes, Tharso ;
de Figueiredo, Celina ;
Kowada, Luis ;
Marquezino, Franklin ;
Posner, Daniel ;
Portugal, Renato .
LATIN 2018: THEORETICAL INFORMATICS, 2018, 10807 :1-13
[6]   Grundy coloring in some subclasses of bipartite graphs and their complements [J].
Verma, Shaily ;
Panda, B. S. .
INFORMATION PROCESSING LETTERS, 2020, 163
[7]   On partial Grundy coloring of bipartite graphs and chordal graphs [J].
Panda, B. S. ;
Verma, Shaily .
DISCRETE APPLIED MATHEMATICS, 2019, 271 :171-183
[8]   Polynomial graph transformability [J].
Kreowski, Hans-Joerg ;
Kuske, Sabine .
THEORETICAL COMPUTER SCIENCE, 2012, 429 :193-201
[9]   ACQUAINTANCE TIME OF A GRAPH [J].
Benjamini, Itai ;
Shinkar, Igor ;
Tsur, Gilad .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2014, 28 (02) :767-785
[10]   Strong transitivity of a graph [J].
Paul, Subhabrata ;
Santra, Kamal .
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2025, 17 (04)
12345