×

On the \(b\)-chromatic number of graphs. (English) Zbl 1024.05026

Kučera, Luděk (ed.), Graph-theoretic concepts in computer science. 28th international workshop, WG 2002, Český Krumlov, Czech Republic, June 13-15, 2002. Revised papers. Berlin: Springer. Lect. Notes Comput. Sci. 2573, 310-320 (2002).
Summary: The \(b\)-chromatic number \(b(G)\) of a graph \(G =(V,E)\) is the largest integer \(k\) such that \(G\) admits a vertex partition into \(k\) independent sets \(X_{i}\) \((i=1,\dots,k)\) such that each \(X_{i}\) contains a vertex \(x_{i }\) adjacent to at least one vertex of each \(X_{j}\), \(j\neq i\). We discuss on the tightness of some bounds on \(b(G)\) and on the complexity of determining \(b(G)\). We also determine the asymptotic behavior of \(b(G_{n,p})\) for the random graph, within the accuracy of a multiplicative factor \(2+o (1)\) as \(n\to\infty\).
For the entire collection see [Zbl 1013.00032].

MSC:

05C15 Coloring of graphs and hypergraphs
05C80 Random graphs (graph-theoretic aspects)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Keywords:

random graph
PDFBibTeX XMLCite
Full Text: Link