|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'506'133
Articles rated: 2609
27 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
The t-tone chromatic number of random graphs | | Deepak Bal
; Patrick Bennett
; Andrzej Dudek
; Alan Frieze
; | | Date: |
2 Oct 2012 | | Abstract: | A proper 2-tone $k$-coloring of a graph is a labeling of the vertices with
elements from $inom{[k]}{2}$ such that adjacent vertices receive disjoint
labels and vertices distance 2 apart receive distinct labels. The 2-tone
chromatic number of a graph $G$, denoted $ au_2(G)$ is the smallest $k$ such
that $G$ admits a proper 2-tone $k$ coloring. In this paper, we prove that
w.h.p. for $pge Cn^{-1/4}ln^{9/4}n$, $ au_2(G_{n,p})=(2+o(1))chi(G_{n,p})$
where $chi$ represents the ordinary chromatic number. For sparse random graphs
with $p=c/n$, $c$ constant, we prove that $ au_2(G_{n,p}) =
lceil{{sqrt{8Delta+1} +5}/{2}}
ceil$ where $Delta$ represents the maximum
degree. For the more general concept of $t$-tone coloring, we achieve similar
results. | | Source: | arXiv, 1210.0635 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER