On the chromatic number of the preferential attachment graph

DOI10.1016/J.EJC.2021.103365MaRDI QIDQ2033902zbMATH OpenOpenAlexFDO

Authors Lyuben Lichev

Publication date 18 June 2021

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

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Emergence of Scaling in Random Networks
• On the chromatic number of random regular graphs
• On the independence number and the chromatic number of generalized preferential attachment models
• Paths in graphs
• Statistical mechanics of complex networks
• Subgraphs in preferential attachment models
• The asymptotic number of labeled graphs with given degree sequences
• The chromatic number of random graphs
• The diameter of a scale-free random graph

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)