Minimum H-decompositions of graphs: edge-critical case
Given a graph \(H\) let \(\phi_{H}(n)\) denote the maximum number of parts that are needed to partition the edge set of any graph on \(n\) vertices such that every member of the partition is either a single edge or isomorphic to \(H\). Furthermore, let \(ex(n,H)\) denote the maximum size of a graph on \(n\) vertices not containing \(H\) as a subgraph. \textit{O. Pikhurko} and \textit{T. Sousa} [``Minimum \(H\)-decompositions of graphs, J. Comb. Theory, Ser. B 97, No.\,6, 1041--1055 (2007; Zbl 1125.05085)] conjectured that \(\phi_{H}(n)=ex(n,H)\) for \(\chi(H) \geq 3\) and all sufficiently large \(n\). Sousa verified the conjecture for clique extensions of order \(r \geq 4\) (\(n \geq r\)) [\textit{T. Sousa}, ``Decompositions of graphs into a given clique-extension, Ars Comb. 100, 465--472 (2011; Zbl 1265.05313)], the cycles of length 5 (\(n \geq 6\)) [\textit{T. Sousa}, ``Decompositions of graphs into 5-cycles and other small graphs, Electron. J. Comb. 12, No. 1, Research paper 49 (2005; Zbl 1079.05044)] and 7 (\(n \geq 10\)) [\textit{T. Sousa}, ``Decomposition of graphs into cycles of length seven and single edges, Ars Comb. (to appear)]. In this paper, the authors verify the conjecture for all edge-critical graphs. They also show that the graphs maximizing \(\phi_{H}(n)\) are \((\chi(H)-1)\)-partite Turán graphs.
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- Asymptotic behavior of the chromatic index for hypergraphs
- Decomposition of graphs into cycles of length seven and single edges.
- Decompositions of graphs into 5-cycles and other small graphs
- scientific article; zbMATH DE number 6093217 (Why is no real title available?)
- scientific article; zbMATH DE number 3641497 (Why is no real title available?)
- scientific article; zbMATH DE number 3258858 (Why is no real title available?)
- scientific article; zbMATH DE number 3262986 (Why is no real title available?)
- Minimum \(H\)-decompositions of graphs
- On complete subgraphs of different orders
- On the structure of linear graphs
- The Representation of a Graph by Set Intersections
- Turán function and H-decomposition problem for gem graphs
- Decomposing uniform hypergraphs into uniform hypertrees and single edges
- Minimum \(H\)-decompositions of graphs
- Turán number and decomposition number of intersecting odd cycles
- Graphs with large maximum degree containing no edge-critical graphs
- A Note on the Minimum H-Subgraph Edge Deletion
- Monochromatic clique decompositions of graphs
- scientific article; zbMATH DE number 568854 (Why is no real title available?)
- Decomposition of graphs into (k,r)-fans and single edges
- Problems and invariants connected with bicliques and multicliques of graphs
- -MINIMUM SPANNING LENGTHS AND AN EXTENSION TO BURNSIDE’S THEOREM ON IRREDUCIBILITY
- Decompositions of graphs into fans and single edges
- Monochromatic \(K_{r}\)-decompositions of graphs
- Minimum rainbow \(H\)-decompositions of graphs
- Minimum rainbow \(H\)-decompositions of graphs
- An improved error term for minimum H-decompositions of graphs
This page was built for publication: Minimum \(H\)-decompositions of graphs: edge-critical case
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q414645)
