A new proof of the independence ratio of triangle-free cubic graphs

DOI10.1016/S0012-365X(00)00242-9zbMath0982.05071OpenAlexW2087063742WikidataQ128081496 ScholiaQ128081496MaRDI QIDQ5936033

Christopher Carl Heckman, Robin Thomas

Publication date: 29 March 2002

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

Full work available at URL: https://doi.org/10.1016/s0012-365x(00)00242-9

zbMATH Keywords

independent settriangle-free graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (22)

The independence number of circulant triangle-free graphs ⋮ New bounds on the independence number of connected graphs ⋮ Lower bounds on the independence number of certain graphs of odd girth at least seven ⋮ Independent sets in \(\{\text{claw}, K_4 \}\)-free 4-regular graphs ⋮ Uniquely restricted matchings in subcubic graphs without short cycles ⋮ The Fractional Chromatic Number of \(\boldsymbol{K_{\Delta }}\)-Free Graphs ⋮ Relating the independence number and the dissociation number ⋮ Independent sets and matchings in subcubic graphs ⋮ Randomly colouring graphs (a combinatorial view) ⋮ On the tightness of the \(\frac {5}{14}\) independence ratio ⋮ Independence, odd girth, and average degree ⋮ Independent sets in graphs ⋮ The fractional chromatic number of triangle-free graphs with \(\varDelta \leq 3\) ⋮ Independent sets in triangle-free cubic planar graphs ⋮ Minimum \(k\)-path vertex cover ⋮ The fractional chromatic number of triangle-free subcubic graphs ⋮ The independence number in graphs of maximum degree three ⋮ Bipartite subgraphs of triangle-free subcubic graphs ⋮ High-girth cubic graphs are homomorphic to the Clebsch graph ⋮ On the Independence Number of Graphs with Maximum Degree 3 ⋮ Subcubic triangle-free graphs have fractional chromatic number at most 14/5 ⋮ On colorings of graph powers

This page was built for publication: A new proof of the independence ratio of triangle-free cubic graphs