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 条

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

Debojyoti Bhattacharya ;

Subhabrata Paul .

Bulletin of the Malaysian Mathematical Sciences Society, 2024, 47

[42] FINDING REGULAR SIMPLE PATHS IN GRAPH DATABASES [J].

MENDELZON, AO ;

WOOD, PT .

SIAM JOURNAL ON COMPUTING, 1995, 24 (06) :1235-1258

[43] Crossing number is hard for cubic graphs [J].

Hlineny, P .

MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2004, PROCEEDINGS, 2004, 3153 :772-782

[44] On the Number of Solutions to a System of Boolean Equations [J].

Leontiev, V. K. ;

Gordeev, E. N. .

AUTOMATION AND REMOTE CONTROL, 2021, 82 (09) :1581-1596

[45] On the Number of Solutions to a System of Boolean Equations [J].

V. K. Leontiev ;

E. N. Gordeev .

Automation and Remote Control, 2021, 82 :1581-1596

[46] On the Hardness of Switching to a Small Number of Edges [J].

Jelinek, Vit ;

Jelinkova, Eva ;

Kratochvil, Jan .

COMPUTING AND COMBINATORICS, COCOON 2016, 2016, 9797 :159-170

[47] COMPLEXITY OF SENTENCES OVER NUMBER RINGS [J].

TUNG, SP .

SIAM JOURNAL ON COMPUTING, 1991, 20 (01) :126-143

[48] Easily searched encodings for number partitioning [J].

Ruml, W ;

Ngo, JT ;

Marks, J ;

Shieber, SM .

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 1996, 89 (02) :251-291

[49] On the Achromatic Number of Certain Distance Graphs [J].

Arul, Sharmila Mary ;

Umamageswari, R. M. .

INTERNATIONAL JOURNAL OF MATHEMATICS AND COMPUTER SCIENCE, 2020, 15 (04) :1187-1192

[50] Crossing number is hard for cubic graphs [J].

Hlineny, P .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2006, 96 (04) :455-471

← 1 2 3 4 5 →