Frick, Marietjie and Katrenič, Peter - Progress on the traceability conjecture for oriented graphs

dmtcs:428 - Discrete Mathematics & Theoretical Computer Science, January 1, 2008, Vol. 10 no. 3
Progress on the traceability conjecture for oriented graphs

Authors: Frick, Marietjie and Katrenič, Peter

A digraph is k-traceable if each of its induced subdigraphs of order k is traceable. The Traceability Conjecture is that for k ≥ 2 every k-traceable oriented graph of order at least 2k − 1 is traceable. The conjecture has been proved for k ≤ 5. We prove that it also holds for k = 6.


Source : oai:HAL:hal-00972339v1
Volume: Vol. 10 no. 3
Section: Graph and Algorithms
Published on: January 1, 2008
Submitted on: March 26, 2015
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Browsing statistics

This page has been seen 23 times.
This article's PDF has been downloaded 51 times.