✦ LIBER ✦

Even Directed Cycles inH-Free Digraphs

✍ Scribed by Anna Galluccio; Martin Loebl

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 176 KB
Volume: 27
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.1997.0910

No coin nor oath required. For personal study only.

✦ Synopsis

A digraph is H-free if its underlying graph does not contain a subgraph contractible to the graph H. We provide a polynomial-time algorithm to solve the even cycle problem in the class of K -free digraphs and in the class of K -free 3, 3 5 digraphs. We also discuss the important role played by the subdivisions of K in 3, 3 solving the even cycle problem in its generality.

📜 SIMILAR VOLUMES

Note on the existence of directed (k + 1

Note on the existence of directed (k + 1)-cycles in diconnected complete k-partite digraphs

✍ R. Balakrishnan; P. Paulraja 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 150 KB 👁 1 views

A graph is constructed to provide a negative answer to the following question of Bondy: Does every diconnected orientation of a complete k-partite (k 2 5) graph with each part of size at least 2 yield a directed (k + 1)-cycle?