An iterative approach to the traceability conjecture for oriented graphs
type: Item
instance of: scholarly article
title: An iterative approach to the traceability conjecture for oriented graphs
zbMATH Open document ID: 1266.05044
author: Jean E. Dunbar
author: Marietjie Frick
author: Joy Singleton
author: Susan Van Aardt
author: A. P. Burger
author: John M. Harris
published in: The Electronic Journal of Combinatorics
publication date: 2013-06-07T00:00:00Z
full work available at URL: v20i1p59
review text: Summary: A digraph is \(k\)-traceable if its order is at least \(k\) and each of its subdigraphs of order \(k\) is traceable. The traceability conjecture (TC) states that for \(k\geq 2\) every \(k\)-traceable oriented graph of order at least \(2k-1\) is traceable. It has been shown that for \(2\leq k\leq 6\), every \(k\)-traceable oriented graph is traceable. We develop an iterative procedure to extend previous results regarding the TC. In particular, we prove that every 7-traceable oriented graph of order at least 9 is traceable and every 8-traceable graph of order at least 14 is traceable.
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 6171898
zbMATH Keywords: traceability conjecture
zbMATH Keywords: path partition conjecture
zbMATH Keywords: oriented graph
zbMATH Keywords: generalized tournament
zbMATH Keywords: traceable
zbMATH Keywords: \(k\)-traceable
zbMATH Keywords: longest path
MaRDI profile type: Publication
Recommended article: A traceability conjecture for oriented graphs
Recommended article: Q3575434
Recommended article: Traceability of \(k\)-traceable oriented graphs
Recommended article: Triangle-free oriented graphs and the traceability conjecture
Recommended article: Computational results on the traceability of oriented graphs of small order
Recommended article: Q3739143
Recommended article: Characterizations of \(k\)-traceable graphs and oriented graphs
Recommended article: Cycles in \(k\)-traceable oriented graphs
Recommended article: Q4542837
Recommended article: On the trace norms of orientations of graphs
description: scientific article; zbMATH DE number 6171898