Name
Abstract | ||
|---|---|---|
A connected vertex ordering of a graph G is an ordering v(1) < v(2) < ... < v(n) of V (G) such that v(i) has at least one neighbour in {v(1),..., v(i-1)}, for every i is an element of {2,..., n}. A connected greedy colouring is a colouring obtained by the greedy algorithm applied to a connected vertex ordering. In this paper we study the parameter Gamma(c)( G), which is the maximum k such that G admits a connected greedy k-colouring, and chi(c)( G), which is the minimum k such that a connected greedy k-colouring of G exists. We prove that computing Gamma(c)(G) is NP-hard for chordal graphs and complements of bipartite graphs. We also prove that if G is bipartite, Gamma(c)(G) = 2. Concerning chi(c)(G), we first show that there is a k-chromatic graph G(k) with chi(c)(G(k)) > chi (G(k)), for every k >= 3. We then prove that for every graph G, chi(c)(G) <= chi(G) + 1. Finally, we prove that deciding if chi(c)(G) = chi(G), given a graph G, is a NP-hard problem. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/978-3-642-54423-1_38 | Lecture Notes in Computer Science |
Keywords | Field | DocType |
Vertex colouring,Greedy colouring,Connected greedy colouring | Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Computer science | Conference |
Volume | ISSN | Citations |
8392 | 0302-9743 | 0 |
PageRank | References | Authors |
0.34 | 7 | 7 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Fabrício Benevides | 1 | 49 | 7.53 |
| Victor Campos | 2 | 8 | 0.95 |
| Mitre Dourado | 3 | 90 | 18.43 |
| Simon Griffiths | 4 | 0 | 0.34 |
| Robert Morris | 5 | 11 | 1.86 |
| Leonardo Sampaio | 6 | 49 | 5.30 |
| Ana Silva | 7 | 25 | 9.56 |