✦ LIBER ✦

Decomposing a Planar Graph into an Independent Set and a 3-Degenerate Graph

✍ Scribed by Carsten Thomassen

Publisher: Elsevier Science
Year: 2001
Tongue: English
Weight: 126 KB
Volume: 83
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.2001.2056

No coin nor oath required. For personal study only.

✦ Synopsis

We prove the conjecture made by O. V. Borodin in 1976 that the vertex set of every planar graph can be decomposed into an independent set and a set inducing a 3-degenerate graph.

📜 SIMILAR VOLUMES

Decomposing a Planar Graph into Degenera

Decomposing a Planar Graph into Degenerate Graphs

✍ C. Thomassen 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 477 KB

We prove the conjecture made by \(\mathrm{O}\). V. Borodin in 1976 that the vertex set of any planar graph can be decomposed into two sets such that one of them induces a 3-degenerate graph and the other induces a 2-degenerate graph. that is, a forest. c. 1995 Academic Press. Inc.

On decomposing a graph into nontrivial b

On decomposing a graph into nontrivial bonds

✍ Sean McGuinness 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 206 KB

We show that for every 2-connected bipartite graph which is not a multiple edge and which has no K 5 -minor there is an edge-disjoint collection of nontrivial bonds (i.e., not stars) which partition the edges of the graph.

An algorithm for finding a large indepen

An algorithm for finding a large independent set in planar graphs

✍ Norishige Chiba; Takao Nishizeki; Nobuji Saito 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 333 KB 👁 1 views

Independent Dominating Sets and a Second

Independent Dominating Sets and a Second Hamiltonian Cycle in Regular Graphs

✍ Carsten Thomassen 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 241 KB

In 1975, John Sheehan conjectured that every Hamiltonian 4-regular graph has a second Hamiltonian cycle. Combined with earlier results this would imply that every Hamiltonian r-regular graph (r 3) has a second Hamiltonian cycle. We shall verify this for r 300.

Generating all 3-connected 4-regular pla

Generating all 3-connected 4-regular planar graphs from the octahedron graph

✍ H. J. Broersma; A. J. W. Duijvestijn; F. Göbel 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 384 KB 👁 1 views

## Abstract We prove that all 3‐connected 4‐regular planar graphs can be generated from the Octahedron Graph, using three operations. We generated these graphs up to 15 vertices inclusive. Moreover, by including a fourth operation we obtain an alternative to a procedure by Lehel to generate all con

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