Random independent sets in triangle-free graphs

DOI10.1017/FMS.2025.10112MaRDI QIDQ6918396zbMATH OpenFDO

Authors Anders Martinsson, Raphael Steiner

Publication date 10 October 2025

Published in Forum of Mathematics, Sigma (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1017/FMS.2025.10112

zbMATH Keywords

fractional coloring with local demandsprobability distributions

Mathematics Subject Classification ID

Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Fractional graph theory, fuzzy graph theory (05C72) Random graphs (graph-theoretic aspects) (05C80) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Cites work

• A note on Ramsey numbers
• A note on the independence number of triangle-free graphs
• A note on the independence number of triangle-free graphs. II
• A short proof of Kneser's conjecture
• Bipartite induced density in triangle-free graphs
• Bounding \(\chi\) by a fraction of \(\Delta\) for graphs without large cliques
• Chromatic number and spectral radius
• Chromatic number of finite and infinite graphs and hypergraphs
• Coloring graphs with sparse neighborhoods
• Coloring triangle-free graphs with local list sizes
• Colouring graphs with forbidden bipartite subgraphs
• Counting colorings of triangle-free graphs
• Dense induced bipartite subgraphs in triangle-free graphs
• Dynamic concentration of the triangle‐free process
• Eigenvalues and colorings of digraphs
• Fractional chromatic number, maximum degree, and girth
• Fractional coloring with local demands and applications to degree-sequence bounds on the independence number
• Graph and hypergraph colouring via nibble methods: a survey
• scientific article; zbMATH DE number 3425628 (Why is no real title available?)
• scientific article; zbMATH DE number 3162927 (Why is no real title available?)
• scientific article; zbMATH DE number 6116733 (Why is no real title available?)
• scientific article; zbMATH DE number 3349875 (Why is no real title available?)
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• scientific article; zbMATH DE number 3050594 (Why is no real title available?)
• scientific article; zbMATH DE number 7788348 (Why is no real title available?)
• Independence numbers of locally sparse graphs and a Ramsey type problem
• Kneser's conjecture, chromatic number, and homotopy
• List packing number of bounded degree graphs
• New eigenvalue bound for the fractional chromatic number
• Occupancy fraction, fractional colouring, and triangle fraction
• On the average size of independent sets in triangle-free graphs
• On the independence number of sparse graphs
• On Turan's theorem for sparse graphs
• Packing list‐colorings
• Separation choosability and dense bipartite induced subgraphs
• Some results on chromatic number as a function of triangle count
• Subcubic triangle-free graphs have fractional chromatic number at most \(14/5\)
• Sur le coloriage des graphs
• Tales of Hoffman: three extensions of Hoffman's bound on the graph chromatic number
• The -Ramsey problem for triangle-free graphs
• The Eigenvalues of a Graph and Its Chromatic Number
• The Independence Ratio of Regular Graphs
• The inertia bound is far from tight
• The list chromatic number of graphs with small clique number
• The triangle-free process and the Ramsey number \(R(3,k)\)
• Uniformly Random Colourings of Sparse Graphs

This page was built for publication: Random independent sets in triangle-free graphs

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