✦ LIBER ✦

Disjoint clique cutsets in graphs without long holes

✍ Scribed by Elaine M. Eschen; Chính T. Hoàng; Mark D. T. Petrick; R. Sritharan

Publisher: John Wiley and Sons
Year: 2005
Tongue: English
Weight: 182 KB
Volume: 48
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20057

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A biclique cutset is a cutset that induces the disjoint union of two cliques. A hole is an induced cycle with at least five vertices. A graph is biclique separable if it has no holes and each induced subgraph that is not a clique contains a clique cutset or a biclique cutset. The class of biclique separable graphs contains several well‐studied graph classes, including triangulated graphs. We prove that for the class of biclique separable graphs, the recognition problem, the vertex coloring problem, and the clique problem can be solved efficiently. Our algorithms also yield a proof that biclique separable graphs are perfect. Our coloring algorithm is actually more general and can be applied to graphs that can be decomposed via a special type of biclique cutset. Our algorithms are based on structural results on biclique separable graphs developed in this paper. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 277–298, 2005

📜 SIMILAR VOLUMES

Edge disjoint Steiner trees in graphs wi

Edge disjoint Steiner trees in graphs without large bridges

✍ Matthias Kriesell 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 150 KB

## Abstract A set __A__ of vertices of an undirected graph __G__ is called __k__‐__edge‐connected in G__ if for all pairs of distinct vertices __a, b__∈__A__, there exist __k__ edge disjoint __a, b__‐paths in __G__. An __A__‐__tree__ is a subtree of __G__ containing __A__, and an __A__‐__bridge__ i

On the diameter ofi-center in a graph wi

On the diameter ofi-center in a graph without long induced paths

✍ Dong, Jinquan 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 117 KB 👁 2 views

A graph G is said to be P t -free if it does not contain an induced path on t vertices. The i-center C i (G) of a connected graph G is the set of vertices whose distance from any vertex in G is at most i. Denote by I(t) the set of natural numbers i, t/2 ≤ i ≤ t -2, with the property that, in every c