On the Caccetta-Häggkvist conjecture with forbidden subgraphs
From MaRDI portal
Publication:2853341
Abstract: The Caccetta-Haggkvist conjecture made in 1978 asserts that every orgraph on n vertices without oriented cycles of length <= l must contain a vertex of outdegree at most (n-1)/l. It has a rather elaborate set of (conjectured) extremal configurations. In this paper we consider the case l=3 that received quite a significant attention in the literature. We identify three orgraphs on four vertices each that are missing as an induced subgraph in all known extremal examples and prove the Caccetta-Haggkvist conjecture for orgraphs missing as induced subgraphs any of these orgraphs, along with cycles of length 3. Using a standard trick, we can also lift the restriction of being induced, although this makes graphs in our list slightly more complicated.
Recommendations
- The Lemmens-Seidel conjecture and forbidden subgraphs
- scientific article; zbMATH DE number 4144022
- Forbidden subgraphs and the König-Egerváry property
- On Seymour's strengthening of Hadwiger's conjecture for graphs with certain forbidden subgraphs
- Forbidden subgraphs and forbidden substructures
- Forbidden subgraphs, stability and hamiltonicity
- Forbidden subgraphs and the Kőnig property
- The number of graphs with large forbidden subgraphs
- scientific article; zbMATH DE number 1185308
- Forbidden subgraphs and bounds on the size of a maximum matching
Cites work
- scientific article; zbMATH DE number 3630786 (Why is no real title available?)
- A note on minimal directed graphs with given girth
- A note on short cycles in digraphs
- Counting subgraphs: A new approach to the Caccetta-Häggkvist conjecture
- Directed triangles in digraphs
- Flag algebras
- Limits of dense graph sequences
- On 3-hypergraphs with forbidden 4-vertex configurations
- On directed triangles in digraphs
- On minimal regular digraphs with given girth
- On the Caccetta-Häggkvist conjecture
- On the Fon-Der-Flaass interpretation of extremal examples for Turán's \((3,4)\)-problem
- On the girth of digraphs
- Proof of the Caccetta-Häggkvist conjecture for oriented graphs with positive minimum out-degree and of independence number two
- Short cycles in digraphs
- Short cycles in directed graphs
- Subgraph densities in signed graphons and the local Simonovits-Sidorenko conjecture
Cited in
(20)- Rainbow cycles for families of matchings
- Degree conditions forcing oriented cycles
- Sparse halves in dense triangle-free graphs
- Forbidden subgraphs and the König-Egerváry property
- On Turán's \((3,4)\)-problem with forbidden subgraphs
- Minimum number of edges that occur in odd cycles
- Minimum Number of Monotone Subsequences of Length 4 in Permutations
- Note on upper bound graphs and forbidden subposets
- Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle
- On the density of transitive tournaments
- 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
- On the Caccetta-Häggkvist conjecture with a forbidden transitive tournament
- The Lemmens-Seidel conjecture and forbidden subgraphs
- A proof of Cunningham's conjecture on restricted subgraphs and jump systems
- Rainbow triangles in three-colored graphs
- Properly colored short cycles in edge-colored graphs
- Decomposing and colouring some locally semicomplete digraphs
- Forbidden configurations for hypohamiltonian graphs
- An Equivalent Version of the Caccetta-Häggkvist Conjecture in an Online Load Balancing Problem
This page was built for publication: On the Caccetta-Häggkvist conjecture with forbidden subgraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2853341)
