Clique coloring of binomial random graphs
Copyright policy )Clique coloring of binomial random graphs
A clique coloring of a graph is a coloring of the vertices so that no maximal clique is monochromatic (ignoring isolated vertices). The smallest number of colors in such a coloring is the clique chromatic number. In this paper, we study the asymptotic behavior of the clique chromatic number of the random graph 𝒢(n,p) for a wide range of edge‐probabilities p = p(n). We see that the typical clique chromatic number, as a function of the average degree, forms an intriguing step function.
[MATH.MATH-PR] Mathematics [math]/Probability [math.PR], Probability (math.PR), Random graphs (graph-theoretic aspects), clique chromatic number, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], Coloring of graphs and hypergraphs, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), random graphs, Mathematics - Probability
[MATH.MATH-PR] Mathematics [math]/Probability [math.PR], Probability (math.PR), Random graphs (graph-theoretic aspects), clique chromatic number, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], Coloring of graphs and hypergraphs, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), random graphs, Mathematics - Probability
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).3 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!