On the independence number and the chromatic number of generalized preferential attachment models

DOI10.1016/j.dam.2020.04.035zbMath1447.05188OpenAlexW3035506051MaRDI QIDQ2197436

Kirill E. Kovalenko

Publication date: 31 August 2020

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2020.04.035

zbMATH Keywords

networksindependence numberchromatic numberpreferential attachmentrandom graph models

Mathematics Subject Classification ID

Applications of graph theory (05C90) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Exact modularity of line graphs of complete graphs, New lower bound on the modularity of Johnson graphs, On the chromatic number of the preferential attachment graph, Lower bounds on the clique-chromatic numbers of some distance graphs

Cites Work

• Local clustering coefficients in preferential attachment models
• Small subgraphs in preferential attachment networks
• Random Kneser graphs and hypergraphs
• Modularity in several random graph models
• On the stability of the independence number of a random subgraph
• On the chromatic numbers of some distance graphs
• Popularity based random graph models leading to a scale-free degree sequence
• Assortativity in generalized preferential attachment models
• Modularity of complex networks models
• Clustering coefficient of a spatial preferential attachment model
• New bounds on clique-chromatic numbers of Johnson graphs
• Modularity of some distance graphs
• New bounds for the clique-chromatic numbers of Johnson graphs
• On threshold probability for the stability of independent sets in distance graphs
• Clique chromatic numbers of intersection graphs
• On the chromatic number of random subgraphs of a certain distance graph
• Large communities in a scale-free network
• Complex networks: structure and dynamics
• Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs
• The degree sequence of a scale-free random graph process
• Generalized Preferential Attachment: Tunable Power-Law Degree Distribution and Clustering Coefficient
• Statistical mechanics of complex networks
• PageRank in Undirected Random Graphs
• Perfect matchings and Hamiltonian cycles in the preferential attachment model
• About the Power Law of the PageRank Vector Component Distribution. Part 1. Numerical Methods for Finding the PageRank Vector
• About the Power Law of the PageRank Vector Component Distribution. Part 2. The Buckley–Osthus Model, Verification of the Power Law for This Model, and Setup of Real Search Engines
• The Maximum Degree of the Barabási–Albert Random Tree
• Local Clustering Coefficient in Generalized Preferential Attachment Models
• The chromatic number of random graphs
• The chromatic number of random graphs