Béla Csaba
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Béla Csaba has a total of 119 co-authors. Here are the top co-authors by number of shared publications:
- András Pluhár
University of Szeged
6 shared publications - Ali Shokoufandeh
Department of Computer Science Drexel University 19105 Philadelphia PA USA
3 shared publications - Judit Jász
Department of Software Engineering, University of Szeged, Szeged, Hungary
3 shared publications - József Balogh
Department of Mathematical Sciences University of Illinois at Urbana-Champaign 61801 Urbana Illinois USA
3 shared publications Lajos Schrettner
University of Szeged
3 shared publications- Tibor Gyimóthy
Department of Software Engineering, University of Szeged, Hungary
3 shared publications
Latest Publications
- 20 May 2025
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 39 (2) , 1201-1212
On the Ramsey–Turán Problem for 4-Cliques
We present an essentially tight bound for the Ramsey–Turán problem for 4-cliques without using the Regularity lemma. This enables us to substantially extend the range in which one has the tight bound for the number of edges in [Formula: see text]-free graphs as a function of the independence number, apart from lower order terms.
- 20 May 2025
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 39 (2) , 1201-1212
On the Ramsey–Turán Problem for 4-Cliques
We present an essentially tight bound for the Ramsey–Turán problem for 4-cliques without using the Regularity lemma. This enables us to substantially extend the range in which one has the tight bound for the number of edges in [Formula: see text]-free graphs as a function of the independence number, apart from lower order terms.
- Open Access
On the Ramsey-Turán problem for 4-cliques
We present an essentially tight bound for the Ramsey-Turán problem for 4-cliques without using the Regularity lemma. This enables us to substantially extend the range in which one has the tight bound for the number of edges in $K_4$-free graphs as a function of the independence number, apart from lower order terms.
Open AccessOn the Ramsey-Turán problem for 4-cliques
We present an essentially tight bound for the Ramsey-Turán problem for 4-cliques without using the Regularity lemma. This enables us to substantially extend the range in which one has the tight bound for the number of edges in $K_4$-free graphs as a function of the independence number, apart from lower order terms.
- Open Access
A discrepancy version of the Hajnal-Szemerédi theorem
A perfect $K_r$-tiling in a graph $G$ is a collection of vertex-disjoint copies of the clique $K_r$ in $G$ covering every vertex of $G$. The famous Hajnal--Szemer\'edi theorem determines the minimum degree threshold for forcing a perfect $K_r$-tiling in a graph $G$. The notion of discrepancy appears in many branches of mathematics. In the graph setting, one assigns the edges of a graph $G$ labels from $\{-1,1\}$, and one seeks substructures $F$ of $G$ that have `high' discrepancy (i.e. the sum of the labels of the edges in $F$ is far from $0$). In this paper we determine the minimum degree threshold for a graph to contain a perfect $K_r$-tiling of high discrepancy.Open AccessA discrepancy version of the Hajnal-Szemerédi theorem
A perfect $K_r$-tiling in a graph $G$ is a collection of vertex-disjoint copies of the clique $K_r$ in $G$ covering every vertex of $G$. The famous Hajnal--Szemer\'edi theorem determines the minimum degree threshold for forcing a perfect $K_r$-tiling in a graph $G$. The notion of discrepancy appears in many branches of mathematics. In the graph setting, one assigns the edges of a graph $G$ labels from $\{-1,1\}$, and one seeks substructures $F$ of $G$ that have `high' discrepancy (i.e. the sum of the labels of the edges in $F$ is far from $0$). In this paper we determine the minimum degree threshold for a graph to contain a perfect $K_r$-tiling of high discrepancy. - Open Access
On the discrepancies of graphs
In the literature, the notion of discrepancy is used in several contexts, even in the theory of graphs. Here, for a graph $G$, $\{-1, 1\}$ labels are assigned to the edges, and we consider a family $\mathcal{S}_G$ of (spanning) subgraphs of certain types, among others spanning trees, Hamiltonian cycles. As usual, we seek for bounds on the sum of the labels that hold for all elements of $\mathcal{S}_G$, for every labeling.Open AccessOn the discrepancies of graphs
In the literature, the notion of discrepancy is used in several contexts, even in the theory of graphs. Here, for a graph $G$, $\{-1, 1\}$ labels are assigned to the edges, and we consider a family $\mathcal{S}_G$ of (spanning) subgraphs of certain types, among others spanning trees, Hamiltonian cycles. As usual, we seek for bounds on the sum of the labels that hold for all elements of $\mathcal{S}_G$, for every labeling. - Open Access
- 9 September 2019
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 35 (6) , 1541-1553
On the Relation of Separability, Bandwidth and Embedding
In this paper we construct a class of bounded degree bipartite graphs with a small separator and large bandwidth, thereby showing that separability and bandwidth are not linearly equivalent. Furthermore, we also prove that graphs from this class are spanning subgraphs of graphs with minimum degree just slightly aboven / 2, even though their bandwidth is large.
- 9 September 2019
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 35 (6) , 1541-1553
Open AccessOn the Relation of Separability, Bandwidth and Embedding
In this paper we construct a class of bounded degree bipartite graphs with a small separator and large bandwidth, thereby showing that separability and bandwidth are not linearly equivalent. Furthermore, we also prove that graphs from this class are spanning subgraphs of graphs with minimum degree just slightly aboven / 2, even though their bandwidth is large.
- Open Access
On embedding degree sequences
Assume that we are given two graphic sequences, $\pi_1$ and $\pi_2$. We consider conditions for $\pi_1$ and $\pi_2$ which guarantee that there exists a simple graph $G_2$ realizing $\pi_2$ such that $G_2$ is the subgraph of any simple graph $G_1$ that realizes $\pi_1$.Open AccessOn embedding degree sequences
Assume that we are given two graphic sequences, $\pi_1$ and $\pi_2$. We consider conditions for $\pi_1$ and $\pi_2$ which guarantee that there exists a simple graph $G_2$ realizing $\pi_2$ such that $G_2$ is the subgraph of any simple graph $G_1$ that realizes $\pi_1$. - 3 January 2019
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 33 (1) , 474-508
Embedding Graphs Having Ore-Degree at Most Five
Let $H$ and $G$ be graphs on $n$ vertices, where $n$ is sufficiently large. We prove that if $H$ has Ore-degree at most 5 and $G$ has minimum degree at least $2n/3$, then $H$ is a subgraph of $G$.- 3 January 2019
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 33 (1) , 474-508
Embedding Graphs Having Ore-Degree at Most Five
Let $H$ and $G$ be graphs on $n$ vertices, where $n$ is sufficiently large. We prove that if $H$ has Ore-degree at most 5 and $G$ has minimum degree at least $2n/3$, then $H$ is a subgraph of $G$.- Open Access
Embedding graphs having Ore-degree at most five
Let $H$ and $G$ be graphs on $n$ vertices, where $n$ is sufficiently large. We prove that if $H$ has Ore-degree at most 5 and $G$ has minimum degree at least $2n/3$ then $H\subset G.$Open AccessEmbedding graphs having Ore-degree at most five
Let $H$ and $G$ be graphs on $n$ vertices, where $n$ is sufficiently large. We prove that if $H$ has Ore-degree at most 5 and $G$ has minimum degree at least $2n/3$ then $H\subset G.$ - 1 November 2016
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 213, 26-33
On the path separation number of graphs
- 1 November 2016
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 213, 26-33
On the path separation number of graphs
- 21 June 2016
- Published by American Mathematical Society (AMS) in Memoirs of the American Mathematical Society
- Vol. 244 (1154)
Proof of the 1-factorization and Hamilton Decomposition Conjectures
In this paper we prove the following results (via a unified approach) for all sufficiently large n n : [ 1 1 -factorization conjecture ] Suppose that n n is even and D ≥ 2 ⌈ n / 4 ⌉ − 1 D\geq 2\lceil n/4\rceil -1 . Then every D D -regular graph G G on n n vertices has a decomposition into perfect matchings. Equivalently, χ ′ ( G ) = D \chi ’(G)=D . [ Hamilton decomposition conjecture ] Suppose that D ≥ ⌊ n / 2 ⌋ D \ge \lfloor n/2 \rfloor . Then every D D -regular graph G G on n n vertices has a decomposition into Hamilton cycles and at most one perfect matching. [ Optimal packings of Hamilton cycles ] Suppose that G G is a graph on n n vertices with minimum degree δ ≥ n / 2 \delta \ge n/2 . Then G G contains at least reg even ( n , δ ) / 2 ≥ ( n − 2 ) / 8 \textrm {reg}_\textrm {even}(n,\delta )/2 \ge (n-2)/8 edge-disjoint Hamilton cycles. Here r e g e v e n ( n , δ ) \mathrm {reg}_{\mathrm {even}}(n,\delta ) denotes the degree of the largest even-regular spanning subgraph one can guarantee in a graph on n n vertices with minimum degree δ \delta . (i) was first explicitly stated by Chetwynd and Hilton. (ii) and the special case δ = ⌈ n / 2 ⌉ \delta = \lceil n/2 \rceil of (iii) answer questions of Nash-Williams from 1970. All of the above bounds are best possible.
- 21 June 2016
- Published by American Mathematical Society (AMS) in Memoirs of the American Mathematical Society
- Vol. 244 (1154)
Proof of the 1-factorization and Hamilton Decomposition Conjectures
In this paper we prove the following results (via a unified approach) for all sufficiently large n n : [ 1 1 -factorization conjecture ] Suppose that n n is even and D ≥ 2 ⌈ n / 4 ⌉ − 1 D\geq 2\lceil n/4\rceil -1 . Then every D D -regular graph G G on n n vertices has a decomposition into perfect matchings. Equivalently, χ ′ ( G ) = D \chi ’(G)=D . [ Hamilton decomposition conjecture ] Suppose that D ≥ ⌊ n / 2 ⌋ D \ge \lfloor n/2 \rfloor . Then every D D -regular graph G G on n n vertices has a decomposition into Hamilton cycles and at most one perfect matching. [ Optimal packings of Hamilton cycles ] Suppose that G G is a graph on n n vertices with minimum degree δ ≥ n / 2 \delta \ge n/2 . Then G G contains at least reg even ( n , δ ) / 2 ≥ ( n − 2 ) / 8 \textrm {reg}_\textrm {even}(n,\delta )/2 \ge (n-2)/8 edge-disjoint Hamilton cycles. Here r e g e v e n ( n , δ ) \mathrm {reg}_{\mathrm {even}}(n,\delta ) denotes the degree of the largest even-regular spanning subgraph one can guarantee in a graph on n n vertices with minimum degree δ \delta . (i) was first explicitly stated by Chetwynd and Hilton. (ii) and the special case δ = ⌈ n / 2 ⌉ \delta = \lceil n/2 \rceil of (iii) answer questions of Nash-Williams from 1970. All of the above bounds are best possible.