The t-tone chromatic number of random graphs

DOI10.1007/S00373-013-1341-9MaRDI QIDQ742618zbMATH OpenOpenAlexWikidataFDO

Authors Deepak Bal, Patrick Bennett, Andrzej Dudek, Alan Frieze

Publication date 19 September 2014

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1210.0635

zbMATH Keywords

random graphstone coloringsvertex labelings

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Random graphs (graph-theoretic aspects) (05C80)

Abstract: A proper 2-tone $k$-coloring of a graph is a labeling of the vertices with elements from $$ 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 $a{u}_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 $pgeC{n}^{-1/4}l{n}^{9/4}n$, $a{u}_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 $a{u}_2(G_{n,p})=lceilsqrt8Delta+1+5/2ceil$ where $Delta$ represents the maximum degree. For the more general concept of $t$-tone coloring, we achieve similar results.

Recommendations

• scientific article; zbMATH DE number 7731183
• 2-tone coloring of graphs with maximum degree 4
• New results in \(t\)-tone coloring of graphs
• The \(t\)-improper chromatic number of random graphs
• The t-improper chromatic number of random graphs

Cites work

• t-tone colorings of graphs
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
• Graph theory
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 3276423 (Why is no real title available?)
• New results in \(t\)-tone coloring of graphs
• Set colourings of graphs

Cited in

(11)

• A lower bound for the t-tone chromatic number of a graph in terms of Wiener index
• New results in \(t\)-tone coloring of graphs
• 2-tone colorings in graph products
• An upper bound for the 3-tone chromatic number of graphs with maximum degree 3
• The t-improper chromatic number of random graphs
• The \(t\)-improper chromatic number of random graphs
• 2-tone coloring of graphs with maximum degree 4
• 2-tone coloring of chordal and outerplanar graphs
• scientific article; zbMATH DE number 7731183 (Why is no real title available?)
• 2-tone coloring of cactus graphs
• The t-tone coloring of some finite planar lattices

This page was built for publication: The \(t\)-tone chromatic number of random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q742618)