Creat membership Creat membership
Sign in

Forgot password?

Confirm
  • Forgot password?
    Sign Up
  • Confirm
    Sign In
Creat membership Creat membership
Sign in

Forgot password?

Confirm
  • Forgot password?
    Sign Up
  • Confirm
    Sign In
Collection
For ¥0.57 per day, unlimited downloads CREATE MEMBERSHIP Download

toTop

If you have any feedback, Please follow the official account to submit feedback.

Turn on your phone and scan

home > search >

Complexity of Grundy coloring and its variants

Author:
Édouard Bonnet  Florent Foucaud  Eun Jung Kim  Florian Sikora  


Journal:
Discrete Applied Mathematics


Issue Date:
2018


Abstract(summary):

Abstract The Grundy number of a graph is the maximum number of colors used by the greedy coloring algorithm over all vertex orderings. In this paper, we study the computational complexity of Grundy Coloring , the problem of determining whether a given graph has Grundy number at least k . We also study the variants Weak Grundy Coloring (where the coloring is not necessarily proper) and Connected Grundy Coloring (where at each step of the greedy coloring algorithm, the subgraph induced by the colored vertices must be connected). We show that Grundy Coloring can be solved in time O ∗ ( 2 . 44 3 n ) and Weak Grundy Coloring in time O ∗ ( 2 . 71 6 n ) on graphs of order n . While Grundy Coloring and Weak Grundy Coloring are known to be solvable in time O ∗ ( 2 O ( wk ) ) for graphs of treewidth w (where k is the number of colors), we prove that under the Exponential Time Hypothesis (ETH), they cannot be solved in time O ∗ ( 2 o ( wlog w ) ) . We also describe an O ∗ ( 2 2 O ( k ) ) algorithm for Weak Grundy Coloring , which is therefore FPT for the parameter k . Moreover, under the ETH, we prove that such a running time is essentially optimal (this lower bound also holds for Grundy Coloring ). Although we do not know whether Grundy Coloring is in FPT , we show that this is the case for graphs belonging to a number of standard graph classes including chordal graphs, claw-free graphs, and graphs excluding a fixed minor. We also describe a quasi-polynomial time algorithm for Grundy Coloring and Weak Grundy Coloring on apex-minor graphs. In stark contrast with the two other problems, we show that Connected Grundy Coloring is NP -complete already for k = 7 colors.


Page:
99-99


VIEW PDF

The preview is over

If you wish to continue, please create your membership or download this.

Create Membership

Similar Literature

Submit Feedback

This function is a member function, members do not limit the number of downloads