𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Recognizing decomposable graphs

✍ Scribed by V. Chvátal

Publisher
John Wiley and Sons
Year
1984
Tongue
English
Weight
129 KB
Volume
8
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A graph is called decomposable if its vertices can be colored red and blue in such a way that each color appears on at least one vertex but each vertex v has at most one neighbor having a different color from v. We point out a simple and efficient algorithm for recognizing decomposable graphs with maximum degree at most 3 and prove that recognizing decomposable graphs with maximum degree 4 is an NP‐complete problem.

📜 SIMILAR VOLUMES

Randomly decomposable graphs
Randomly decomposable graphs
✍ Sergio Ruiz 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 362 KB

A nonempty graph G is randomly H-decomposable if every family of edge-disjoint subgraphs of G, each subgraph isomorphic to H, can be extended to an H-decomposition of G. A characterization of those randomly H-decomposable graphs is given whenever H has two edges. Some related questions are discussed

Recognizing locally equivalent graphs
Recognizing locally equivalent graphs
✍ André Bouchet 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 771 KB

Bouchet, A., Recognizing locally equivalent graphs, Discrete Mathematics 114 (1993) 75-86. To locally complement a simple graph Fat one of its vertices u is to replace the subgraph induced by F on n(o)= {w: w is an edge of F} by the complementary subgraph. Graphs related by a sequence of local comp

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.

Decomposing graphs under degree constrai
Decomposing graphs under degree constraints
✍ Stiebitz, Michael 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 246 KB

We prove a conjecture of C. Thomassen: If s and t are non-negative integers, and if G is a graph with minimum degree s + t + 1, then the vertex set of G can be partitioned into two sets which induce subgraphs of minimum degree at least s and t , respectively.

Decomposing Ends of Locally Finite Graph
Decomposing Ends of Locally Finite Graphs
✍ Heinz Adolf Jung; Peter Niemeyer 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 905 KB

An important invariant of translations of infinite locally finite graphs is that of a direction as introduced by HALIN. This invariant gives not much information if the translation is not a proper one. A new refined concept of directions is investigated. A double ray D of a graph X is said to be me