Linear colouring of binomial random graphs

DOI10.1016/j.disc.2024.114278MaRDI QIDQ6646401

Paweł Prałat, Austin Eide

Publication date: 2 December 2024

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

zbMATH Keywords

random graphslinear colouring

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sparsity. Graphs, structures, and algorithms
• On low tree-depth decompositions
• Critical random graphs: Diameter and mixing time
• The longest path in a random graph
• Hamiltonian circuits in random graphs
• On the order of countable graphs
• Linear coloring of graphs
• Orderings on graphs and game coloring number
• Polynomial treedepth bounds in linear colorings
• On the tree-depth of random graphs
• Tree-depth, subgraph coloring and homomorphism bounds
• Meyniel's conjecture holds for random graphs
• Cores of random graphs are born Hamiltonian
• Introduction to Random Graphs
• Hamiltonicity thresholds in Achlioptas processes
• Graph Theory and Probability
• Acyclic coloring of graphs
• Meyniel's conjecture holds for random d‐regular graphs
• Improved Bounds for the Excluded-Minor Approximation of Treedepth
• Almost all 5‐regular graphs have a 3‐flow

This page was built for publication: Linear colouring of binomial random graphs