On the chromatic number of the preferential attachment graph

DOI10.1016/J.EJC.2021.103365zbMATH Open1466.05073arXiv2008.00871OpenAlexW3166317815MaRDI QIDQ2033902FDOQ2033902

Authors: Lyuben Lichev 

Publication date: 18 June 2021

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: We prove that for every $minmathbbN$ and every $deltain(-m,0)$, the chromatic number of the preferential attachment graph $P{A}_t(m,delta)$ is asymptotically almost surely equal to $m+1$. The proof relies on a combinatorial construction of a family of digraphs of chromatic number $m+1$ followed by a proof that asymptotically almost surely there is a digraph in this family, which is realised as a subgraph of the preferential attachment graph.

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

Recommendations

• On the independence number and the chromatic number of generalized preferential attachment models
• On the chromatic number of graphs
• scientific article; zbMATH DE number 77956
• On chromatic‐choosable graphs
• scientific article; zbMATH DE number 742642
• The chromatic connectivity of graphs
• scientific article; zbMATH DE number 4108789
• On the total set chromatic number of graphs
• scientific article; zbMATH DE number 3245178
• Precoloring extension on chordal graphs

zbMATH Keywords

maximal independent setrandom graph model

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Statistical mechanics of complex networks
• Emergence of Scaling in Random Networks
• Title not available (Why is that?)
• Title not available (Why is that?)
• Paths in graphs
• The diameter of a scale-free random graph
• Title not available (Why is that?)
• The asymptotic number of labeled graphs with given degree sequences
• The chromatic number of random graphs
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• On the chromatic number of random regular graphs
• On the independence number and the chromatic number of generalized preferential attachment models
• Subgraphs in preferential attachment models

This page was built for publication: On the chromatic number of the preferential attachment graph

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