Abstract
We describe a way of assigning labels to the vertices of any undirected graph on up to n vertices, each composed of n/2+ O(1) bits, such that given the labels of two vertices, and no other information regarding the graph, it is possible to decide whether or not the vertices are adjacent in the graph. This is optimal, up to an additive constant, and constitutes the first improvement in almost 50 years of an n/2+O(log n) bound of Moon. As a consequence, we obtain an induced-universal graph for n-vertex graphs containing only O(2n/2) vertices, which is optimal up to a multiplicative constant, solving an open problem of Vizing from 1968. We obtain similar tight results for directed graphs, tournaments and bipartite graphs.
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015 : STOC '15 |
| Number of pages | 10 |
| Publisher | Association for Computing Machinery |
| Publication date | 14 Jun 2015 |
| Pages | 625-634 |
| ISBN (Print) | 978-1-4503-3536-2 |
| DOIs | |
| Publication status | Published - 14 Jun 2015 |
| Event | Annual ACM Symposium on the Theory of Computing 2015 - Portland, United States Duration: 15 Jun 2015 → 17 Jun 2015 Conference number: 47 |
Conference
| Conference | Annual ACM Symposium on the Theory of Computing 2015 |
|---|---|
| Number | 47 |
| Country/Territory | United States |
| City | Portland |
| Period | 15/06/2015 → 17/06/2015 |