𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Berge graphs with chordless cycles of bounded length

✍ Scribed by Rusu, Irena

Publisher
John Wiley and Sons
Year
1999
Tongue
English
Weight
82 KB
Volume
32
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

A graph is called weakly triangulated if it contains no chordless cycle on five or more vertices (also called hole) and no complement of such a cycle (also called antihole). Equivalently, we can define weakly triangulated graphs as antihole-free graphs whose induced cycles are isomorphic either to C 3 or to C 4 .

The perfection of weakly triangulated graphs was proved by Hayward [Hayward, J Combin Theory B. 39 (1985), 200-208] and generated intense studies to efficiently solve, for these graphs, the classical NP-complete problems that become polynomial on perfect graphs. If we replace, in the definition above, the C 4 by an arbitrary C p (p even, at least equal to 6), we obtain new classes of graphs whose perfection is shown in this article. In fact, we prove a more general result: for any even integer p β‰₯ 6, the graphs whose cycles are isomorphic either to C 3 or to one of C p , C p+2 , . . . , C 2p-6 are perfect.

πŸ“œ SIMILAR VOLUMES

Extremal graphs with bounded densities o
Extremal graphs with bounded densities of small subgraphs
✍ Griggs, Jerrold R.; Simonovits, MiklοΏ½os; Thomas, George Rubin πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 373 KB πŸ‘ 1 views

Let Ex(n, k, Β΅) denote the maximum number of edges of an n-vertex graph in which every subgraph of k vertices has at most Β΅ edges. Here we summarize some known results of the problem of determining Ex(n, k, Β΅), give simple proofs, and find some new estimates and extremal graphs. Besides proving new

Partitions of a graph into paths with pr
Partitions of a graph into paths with prescribed endvertices and lengths
✍ Hikoe Enomoto; Katsuhiro Ota πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 95 KB

For a graph G, let ' 2 (G ) denote the minimum degree sum of a pair of nonadjacent vertices. We conjecture that if |V(G)| n i 1 k a i and ' 2 (G ) ! n k Γ€ 1, then for any k vertices v 1 , v 2 , F F F , v k in G, there exist vertex-disjoint paths P 1 , P 2 , F F F , P k such that |V (P i )| a i and v

Apoptosis induced with different cycle-p
Apoptosis induced with different cycle-perturbing agents produces differential changes in the fluorescence lifetime of DNA-bound ethidium bromide
✍ B. L. Sailer; J. G. Valdez; J. A. Steinkamp; H. A. Crissman πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 175 KB

Fluorescence lifetime analysis was used in combination with conventional flow cytometric analysis to monitor changes in residual chromatin in apoptotic HL-60 cell populations following treatment with camptothecin, cycloheximide, genistein, H7, and gamma radiation. Data presented show that all of the