# Regular decomposition of the edge set of graphs with applications

@inproceedings{Csaba2021RegularDO, title={Regular decomposition of the edge set of graphs with applications}, author={B{\'e}la Csaba}, year={2021} }

We introduce a new method for decomposing the edge set of a graph, and use it to replace the Regularity lemma of Szemerédi in some graph embedding problems. An algorithmic version is also given.

#### References

SHOWING 1-10 OF 28 REFERENCES

Szemeredi''s Regularity Lemma and its applications in graph theory

- Mathematics
- 1995

Szemer\''edi''s Regularity Lemma is an important tool in discrete mathematics. It says that, in some sense, all graphs can be approximated by random-looking graphs. Therefore the lemma helps in… Expand

The Algorithmic Aspects of the Regularity Lemma

- Computer Science, Mathematics
- J. Algorithms
- 1994

The computational difficulty of finding a regular partition is demonstrated; it is shown that deciding if a given partition of an input graph satisfies the properties guaranteed by the lemma is co-NP-complete; and it is proved that despite this difficulty the regularity lemma can be made constructive. Expand

Triple systems with no six points carrying three triangles

- Combinatorics (Keszthely, 1976), 18
- 1978

The regularity method for graphs with few 4‐cycles

- Mathematics
- Journal of the London Mathematical Society
- 2021

We develop a sparse graph regularity method that applies to graphs with few 4-cycles, including new counting and removal lemmas for 5-cycles in such graphs. Some applications include:
* Every… Expand

Bounds for graph regularity and removal lemmas

- Mathematics, Computer Science
- ArXiv
- 2011

It is shown that a weak partition with approximation parameter Epsilon may require as many as 2^{\Omega}(\epsilon^{-2}) parts, which is tight up to the implied constant and solves a problem studied by Lovász and Szegedy. Expand

A new graph decomposition method for bipartite graphs

- Mathematics
- 2021

Given a sufficiently large and sufficiently dense bipartite graph G = (A,B;E), we present a novel method for decomposing the majority of the edges of G into quasirandom graphs so that the vertex sets… Expand

Triangles in C5‐free graphs and hypergraphs of girth six

- Mathematics
- Journal of Graph Theory
- 2021

We introduce a new approach and prove that the maximum number of triangles in a $C_5$-free graph on $n$ vertices is at most $$(1 + o(1)) \frac{1}{3 \sqrt 2} n^{3/2}.$$ We also show a connection to… Expand

A note on the maximum number of triangles in a C5-free graph

- Mathematics, Computer Science
- J. Graph Theory
- 2019

We prove that the maximum number of triangles in a C5-free graph on n vertices is at most [Formula presented](1+o(1))n3/2, improving an estimate of Alon and Shikhelman [Alon, N. and C. Shikhelman,… Expand

A blow-up lemma for approximate decompositions

- Mathematics
- Transactions of the American Mathematical Society
- 2018

<p>We develop a new method for constructing approximate decompositions of dense graphs into sparse graphs and apply it to long-standing decomposition problems. For instance, our results imply the… Expand

Resolution of the Oberwolfach problem

- Mathematics
- Journal of the European Mathematical Society
- 2018

The Oberwolfach problem, posed by Ringel in 1967, asks for a decomposition of $K_{2n+1}$ into edge-disjoint copies of a given $2$-factor. We show that this can be achieved for all large $n$. We… Expand