✦ LIBER ✦

Recognizing sign solvable graphs

✍ Scribed by Pierre Hansen

Book ID: 104182748
Publisher: Elsevier Science
Year: 1983
Tongue: English
Weight: 307 KB
Volume: 6
Category: Article
ISSN: 0166-218X
DOI: 10.1016/0166-218x(83)90079-3

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Sign solvable graphs

✍ John S. Maybee 📂 Article 📅 1980 🏛 Elsevier Science 🌐 English ⚖ 723 KB

Recognizing Berge Graphs

✍ Maria Chudnovsky*; Gérard Cornuéjols**; Xinming Liu†; Paul Seymour†; Kristina Vu 📂 Article 📅 2005 🏛 Springer-Verlag 🌐 English ⚖ 490 KB

Recognizing decomposable graphs

✍ V. Chvátal 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 129 KB

## 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

Conditional sign-solvability

✍ Richard A. Brualdi; Keith L. Chavey; Bryan L. Shader 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 656 KB

Recognizing quasi-triangulated graphs

✍ Jeremy P Spinrad 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 206 KB

This paper discusses a method for recognizing certain graph classes based on elimination schemes more e ciently. We reduce the time bound for recognizing quasi-triangulated graphs from O(n 3 ) to O(n 2:77 ), and perfect elimination bipartite and cop-win graphs from O(n 3 ) to O(n 3 =log n).

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