Improving the Caro-Wei bound and applications to Turán stability

DOI10.1016/J.DAM.2024.06.006zbMATH Open1547.05226MaRDI QIDQ6611049

Tom Kelly, Luke Postle

Publication date: 26 September 2024

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

zbMATH Keywords

independence numberBrooks' theoremCaro-Wei theoremsimplicial verticesTurán stability

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A lower bound on the independence number of a graph in terms of degrees and local clique sizes
• On bounds for some graph invariants
• A proof of the stability of extremal graphs, Simonovits' stability from Szemerédi's regularity
• Independence in connected graphs
• A stability theorem for maximal \(K_{r+1}\)-free graphs
• A note on the independence number of triangle-free graphs
• A note on Ramsey numbers
• A note on the independence number of triangle-free graphs. II
• A probabilistic lower bound on the independence number of graphs
• Lower bounds on the independence number in terms of the degrees
• Large generalized books are \(p\)-good
• New potential functions for greedy independence and coloring
• On Selkow's bound on the independence number of graphs
• Eine Extremalaufgabe aus der Graphentheorie.
• Some new results in extremal graph theory
• The potential of greed for independence
• Turán's theorem and k‐connected graphs
• A lower bound on the independence number of a graph in terms of degrees
• Strong Turán stability
• On the independence number of a graph in terms of order and size

Related Items (1)

Fractional coloring with local demands and applications to degree-sequence bounds on the independence number

This page was built for publication: Improving the Caro-Wei bound and applications to Turán stability

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