Directed triangles in digraphs

DOI10.1006/JCTB.1998.1839MaRDI QIDQ1127878zbMATH OpenOpenAlexFDO

Authors J. Shen

Publication date 10 September 1998

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/95818e50f27eac79a67958f4509616b3694f771c

zbMATH Keywords

digraphdirected triangleminimum outdegree

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38)

Review text

Let \(c\) be the smallest possible value such that every digraph on \(n\) vertices with minimum outdegree at least \(cn\) contains a directed triangle. It was conjectured by Caccetta and Häggkvist in 1978 that \(c=1/3\). Recently Bondy showed that \(c\leq (2\sqrt{6}- 3)/5= 0.3797\ldots\) by using some counting arguments. In this note, we prove that \(c\leq 3-\sqrt{7}= 0.3542\ldots\).

Recommendations

• On directed triangles in digraphs
• On the Caccetta-Häggkvist conjecture
• scientific article; zbMATH DE number 6263412

Cites work

• Counting subgraphs: A new approach to the Caccetta-Häggkvist conjecture
• Directed triangles in directed graphs
• scientific article; zbMATH DE number 3861195 (Why is no real title available?)
• scientific article; zbMATH DE number 3630786 (Why is no real title available?)
• On minimal regular digraphs with given girth

Cited in

(25)

• On directed triangles in digraphs
• Digraphs without directed path of length two or three
• Some approaches to a conjecture on short cycles in digraphs
• On Sullivan's conjecture on cycles in 4-free and 5-free digraphs
• Properly colored short cycles in edge-colored graphs
• Rainbow triangles in edge-colored graphs
• Short cycles in oriented graphs
• On the Caccetta-Häggkvist conjecture with forbidden subgraphs
• On the Chudnovsky-Seymour-Sullivan conjecture on cycles in triangle-free digraphs
• An Equivalent Version of the Caccetta-Häggkvist Conjecture in an Online Load Balancing Problem
• The Binding Number of a Digraph
• Rainbow \(C_3\)'s and \(C_4\)'s in edge-colored graphs
• Color degree and heterochromatic cycles in edge-colored graphs
• On short cycles in triangle-free oriented graphs.
• On the Caccetta-Häggkvist conjecture with a forbidden transitive tournament
• The binding number of a digraph and its computation
• Directed triangles in directed graphs
• Independent directed triangles in a directed graph
• Short rainbow cycles in graphs and matroids
• Path-monochromatic bounded depth rooted trees in (random) tournaments
• Degree conditions forcing oriented cycles
• Bounds on the acyclic disconnection of a digraph
• Subgraphs with a positive minimum semidegree in digraphs with large outdegree
• A new bound for a particular case of the Caccetta-Häggkvist conjecture
• Cycles of given length in oriented graphs

This page was built for publication: Directed triangles in digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1127878)