✦ LIBER ✦

Edge density and independence ratio in triangle-free graphs with maximum degree three

✍ Scribed by Jerrold Griggs; Owen Murphy

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 548 KB
Volume: 152
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)00263-i

No coin nor oath required. For personal study only.

✦ Synopsis

A simple polynomial-time algorithm is presented which computes independent sets of guaranteed size in connected triangle-free noncubic graphs with maximum degree 3. Let nand m denote the number of vertices and edges, respectively, and let c '= m/n denote the edge density where c < 3/2. The algorithm establishes new lower bounds on the independence ratio of these graphs for 1 < c < 3/2.

📜 SIMILAR VOLUMES

Size and independence in triangle-free g

Size and independence in triangle-free graphs with maximum degree three

✍ Kathryn Fraughnaugh Jones 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 549 KB

## Abstract Let __C__ be the class of triangle‐free graphs with maximum degree at most three. A lower bound for the number of edges in a graph of __C__ is derived in terms of the number of vertices and the independence. Several classes of graphs for which this bound is attained are given. As coroll

Largest bipartite subgraphs in triangle-

Largest bipartite subgraphs in triangle-free graphs with maximum degree three

✍ J. A. Bondy; S. C. Locke 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 977 KB

Let G be a triangle-free, loopless graph with maximum degree three. We display a polynomi$ algorithm which returns a bipartite subgraph of G containing at least 5 of the edges of G. Furthermore, we characterize the dodecahedron and the Petersen graph as the only 3-regular, triangle-free, loopless, c

Triangle-free eulerian tours in graphs w

Triangle-free eulerian tours in graphs with maximum degree at most 4

✍ Tobias Adelgren 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 351 KB

Very rapidly mixing Markov chains for 2Δ

Very rapidly mixing Markov chains for 2Δ-colorings and for independent sets in a graph with maximum degree 4

✍ Michael Molloy 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 140 KB 👁 1 views

We introduce a new technique for analyzing the mixing rate of Markov chains. We use it to prove that the Glauber dynamics on 2 -colorings of a graph with maximum degree mixes in O n log n time. We prove the same mixing rate for the Insert/Delete/Drag chain of Dyer and Greenhill (Random Structures A