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 条

[21] On some weighted satisfiability and graph problems [J].

Porschen, S .

SOFSEM 2005:THEORY AND PRACTICE OF COMPUTER SCIENCE, 2005, 3381 :278-287

[22] THE ORIENTATION OF MODULES BASED ON GRAPH DECOMPOSITION [J].

CHENG, CK ;

YAO, SZ ;

HU, TC .

IEEE TRANSACTIONS ON COMPUTERS, 1991, 40 (06) :774-780

[23] Graph Linear Notations with Regular Expressions [J].

Mimura, Ren ;

Miyamoto, Kengo ;

Fujiyoshi, Akio .

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2024, E107D (03) :312-319

[24] Augmenting the Rigidity of a Graph in R 2 [J].

Garcia, A. ;

Tejel, J. .

ALGORITHMICA, 2011, 59 (02) :145-168

[25] RECONTAMINATION DOES NOT HELP TO SEARCH A GRAPH [J].

LAPAUGH, AS .

JOURNAL OF THE ACM, 1993, 40 (02) :224-245

[26] Flip Distances Between Graph Orientations [J].

Aichholzer, Oswin ;

Cardinal, Jean ;

Huynh, Tony ;

Knauer, Kolja ;

Mutze, Torsten ;

Steiner, Raphael ;

Vogtenhuber, Birgit .

ALGORITHMICA, 2021, 83 (01) :116-143

[27] Approximate graph coloring by semidefinite programming [J].

Karger, D ;

Motwani, R ;

Sudan, M .

JOURNAL OF THE ACM, 1998, 45 (02) :246-265

[28] The circular chromatic number of a digraph [J].

Bokal, D ;

Fijavz, G ;

Juvan, M ;

Kayll, PM ;

Mohar, B .

JOURNAL OF GRAPH THEORY, 2004, 46 (03) :227-240

[29] Some results on the achromatic number [J].

Cairnie, N ;

Edwards, K .

JOURNAL OF GRAPH THEORY, 1997, 26 (03) :129-136

[30] Approximation algorithms for the achromatic number [J].

Chaudhary, A ;

Vishwanathan, S .

JOURNAL OF ALGORITHMS, 2001, 41 (02) :404-416

← 1 2 3 4 5 →