Counting flags in triangle-free digraphs

DOI10.1016/j.endm.2009.07.105zbMath1273.05107arXiv0908.2791OpenAlexW4233663723WikidataQ57601455 ScholiaQ57601455MaRDI QIDQ5891231

Jan Hladký, Serguei Norine, Daniel Král'

Publication date: 10 October 2013

Published in: Electronic Notes in Discrete Mathematics, Combinatorica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0908.2791

zbMATH Keywords

digraphsflags

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Directed graphs (digraphs), tournaments (05C20)

Related Items (26)

Paths of length three are \(K_{r+1}\)-Turán-good ⋮ Rainbow triangles in three-colored graphs ⋮ Proof of the Caccetta-Häggkvist conjecture for oriented graphs with positive minimum out-degree and of independence number two ⋮ Short rainbow cycles in graphs and matroids ⋮ Improved bounds for the triangle case of Aharoni's rainbow generalization of the Caccetta-Häggkvist conjecture ⋮ Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle ⋮ A survey on Hamilton cycles in directed graphs ⋮ Solving Turán's tetrahedron problem for the ℓ2$\ell _2$‐norm ⋮ 4-Free Strong Digraphs with the Maximum Size ⋮ On Sullivan's conjecture on cycles in 4-free and 5-free digraphs ⋮ On Multicolor Ramsey Numbers of Triple System Paths of Length 3 ⋮ Nonuniform Degrees and Rainbow Versions of the Caccetta–Häggkvist Conjecture ⋮ Minimum Number of Monotone Subsequences of Length 4 in Permutations ⋮ A new lower bound based on Gromov's method of selecting heavily covered points ⋮ Short directed cycles in bipartite digraphs ⋮ On the Caccetta-Häggkvist conjecture with a forbidden transitive tournament ⋮ The Inducibility of Graphs on Four Vertices ⋮ A new bound for a particular case of the Caccetta-Häggkvist conjecture ⋮ Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube ⋮ 3-free strong digraphs with the maximum size ⋮ Decomposing Graphs into Edges and Triangles ⋮ Minimum number of edges that occur in odd cycles ⋮ Properly colored short cycles in edge-colored graphs ⋮ Compactness and finite forcibility of graphons ⋮ Inducibility of directed paths ⋮ On the Caccetta-Häggkvist Conjecture with Forbidden Subgraphs

Cites Work

• Unnamed Item
• Monochromatic triangles in three-coloured graphs
• Destroying cycles in digraphs
• On the maximum number of five-cycles in a triangle-free graph
• A problem of Erdős on the minimum number of \(k\)-cliques
• Limits of dense graph sequences
• Cycles in dense digraphs
• On directed triangles in digraphs
• Directed triangles in digraphs
• Counting subgraphs: A new approach to the Caccetta-Häggkvist conjecture
• On the number of pentagons in triangle-free graphs
• On the Caccetta-Häggkvist Conjecture with Forbidden Subgraphs
• Random graphons and a weak Positivstellensatz for graphs
• Non-Three-Colourable Common Graphs Exist
• On 3-Hypergraphs with Forbidden 4-Vertex Configurations
• Hypergraphs Do Jump
• On the Minimal Density of Triangles in Graphs
• A New Bound for the 2/3 Conjecture
• Undecidability of linear inequalities in graph homomorphism densities
• Minimum Number ofk-Cliques in Graphs with Bounded Independence Number
• Flag algebras

This page was built for publication: Counting flags in triangle-free digraphs