Name
Abstract | ||
|---|---|---|
Let c : E(G) -> [k] be a colouring, not necessarily proper, of edges of a graph G. For a vertex v is an element of V , let (c) over bar (v) = (a(1) ,...,a(k)), where a(i) = vertical bar{u : uv is an element of E(G),c(uv) = i}vertical bar , for i is an element of[k]. If we re-order the sequence (c) over bar (v) non-decreasingly, we obtain a sequence c*(v) = (d(1),...,d(k)) , called a palette of a vertex v . This can be viewed as the most comprehensive information about colours incident with v which can be delivered by a person who is unable to name colours but distinguishes one from another. The smallest k such that c* is a proper colouring of vertices of G is called the colour-blind index of a graph G , and is denoted by dal(G) . We conjecture that there is a constant K such that dal(G) <= K for every graph G for which the parameter is well defined. As our main result we prove that K <= 6 for regular graphs of sufficiently large degree, and for irregular graphs with delta(G) and Delta(G) satisfying certain conditions. The proofs are based on the Lopsided Lovasz Local Lemma. We also show that K = 3 for all regular bipartite graphs, and for complete graphs of order n >= 8 . |
Year | Venue | Keywords |
|---|---|---|
2013 | ELECTRONIC JOURNAL OF COMBINATORICS | graph colouring,distinguishing adjacent vertices,Lovasz Local Lemma |
Field | DocType | Volume |
Graph,Discrete mathematics,Combinatorics,Vertex (geometry),Graph colouring,Lovász local lemma,Conjecture,Mathematics | Journal | 20.0 |
Issue | ISSN | Citations |
3.0 | 1077-8926 | 2 |
PageRank | References | Authors |
0.40 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Rafał Kalinowski | 1 | 48 | 10.75 |
| Monika Pilsniak | 2 | 29 | 5.42 |
| Jakub Przybyło | 3 | 210 | 27.55 |
| Mariusz Wozniak | 4 | 111 | 19.51 |