The t-Tone Chromatic Number of Random Graphs

Deepak Bal, Patrick Bennett, Andrzej Dudek, Alan Frieze

Research output: Contribution to journalArticle

3 Citations (Scopus)

Abstract

A proper 2-tone k-coloring of a graph is a labeling of the vertices with elements from (formula presented.) 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 τ 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 (formula presented.) where X represents the ordinary chromatic number. For sparse random graphs with p = c/n, c constant, we prove that (formula presented.) where Δ represents the maximum degree. For the more general concept of t-tone coloring, we achieve similar results.

Original languageEnglish
Pages (from-to)1073-1086
Number of pages14
JournalGraphs and Combinatorics
Volume30
Issue number5
DOIs
StatePublished - 1 Jan 2014

Fingerprint

Coloring
Chromatic number
Random Graphs
Colouring
Labels
Sparse Graphs
Graph in graph theory
Maximum Degree
Labeling
Disjoint
Adjacent
Distinct

Keywords

  • Random graphs
  • Tone colorings
  • Vertex labelings

Cite this

Bal, Deepak ; Bennett, Patrick ; Dudek, Andrzej ; Frieze, Alan. / The t-Tone Chromatic Number of Random Graphs. In: Graphs and Combinatorics. 2014 ; Vol. 30, No. 5. pp. 1073-1086.
@article{b437a03ea02049089a4b33abc99791c6,
title = "The t-Tone Chromatic Number of Random Graphs",
abstract = "A proper 2-tone k-coloring of a graph is a labeling of the vertices with elements from (formula presented.) 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 τ 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 (formula presented.) where X represents the ordinary chromatic number. For sparse random graphs with p = c/n, c constant, we prove that (formula presented.) where Δ represents the maximum degree. For the more general concept of t-tone coloring, we achieve similar results.",
keywords = "Random graphs, Tone colorings, Vertex labelings",
author = "Deepak Bal and Patrick Bennett and Andrzej Dudek and Alan Frieze",
year = "2014",
month = "1",
day = "1",
doi = "10.1007/s00373-013-1341-9",
language = "English",
volume = "30",
pages = "1073--1086",
journal = "Graphs and Combinatorics",
issn = "0911-0119",
publisher = "Springer Japan",
number = "5",

}

Bal, D, Bennett, P, Dudek, A & Frieze, A 2014, 'The t-Tone Chromatic Number of Random Graphs', Graphs and Combinatorics, vol. 30, no. 5, pp. 1073-1086. https://doi.org/10.1007/s00373-013-1341-9

The t-Tone Chromatic Number of Random Graphs. / Bal, Deepak; Bennett, Patrick; Dudek, Andrzej; Frieze, Alan.

In: Graphs and Combinatorics, Vol. 30, No. 5, 01.01.2014, p. 1073-1086.

Research output: Contribution to journalArticle

TY - JOUR

T1 - The t-Tone Chromatic Number of Random Graphs

AU - Bal, Deepak

AU - Bennett, Patrick

AU - Dudek, Andrzej

AU - Frieze, Alan

PY - 2014/1/1

Y1 - 2014/1/1

N2 - A proper 2-tone k-coloring of a graph is a labeling of the vertices with elements from (formula presented.) 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 τ 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 (formula presented.) where X represents the ordinary chromatic number. For sparse random graphs with p = c/n, c constant, we prove that (formula presented.) where Δ represents the maximum degree. For the more general concept of t-tone coloring, we achieve similar results.

AB - A proper 2-tone k-coloring of a graph is a labeling of the vertices with elements from (formula presented.) 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 τ 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 (formula presented.) where X represents the ordinary chromatic number. For sparse random graphs with p = c/n, c constant, we prove that (formula presented.) where Δ represents the maximum degree. For the more general concept of t-tone coloring, we achieve similar results.

KW - Random graphs

KW - Tone colorings

KW - Vertex labelings

UR - http://www.scopus.com/inward/record.url?scp=84906345851&partnerID=8YFLogxK

U2 - 10.1007/s00373-013-1341-9

DO - 10.1007/s00373-013-1341-9

M3 - Article

AN - SCOPUS:84906345851

VL - 30

SP - 1073

EP - 1086

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

SN - 0911-0119

IS - 5

ER -