Z. Tuza

activity

20042026

most citedComputing all possible graph structures describing linearly conjugate realizations of kinetic systems

16 citations · 50 across the 58 of their papers we have counts for

collaborators

Showing math.COShow all

60 papers · 1 filter

math.CO2026

The strong (non-induced) Turán numbers

Yair Caro, Zsolt Tuza

In this paper we introduce and explore the following new graph invariant: For a graph $G$ on $k$ vertices, $G \neq = K_{k}$ , let $s t (n, G)$ denote the maximum number of edges in a graph…

math.CO2026

Induced/Incomparable versus Ramsey

Yair Caro, Zsolt Tuza, Christina Zarb

We consider the following problem: Let $H$ and $F$ be two graphs on $k$ vertices and assume $F \neq = H$ . We say that $H$ and $F$ are incomparable if neither $F$ nor $H$ contains the…

math.CO2025

The odd independence number of graphs, II: Finite and infinite grids and chessboard graphs

Yair Caro, Mirko Petruševski, Riste Škrekovski +1

An odd independent set $S$ in a graph $G = (V, E)$ is an independent set of vertices such that, for every vertex $v \in V ∖ S$ , either $N (v) \cap S = \emptyset$ or $|N(v) \cap…

math.CO2025

The odd independence number of graphs, I: Foundations and classical classes

Yair Caro, Mirko Petruševski, Riste Škrekovski +1

An odd independent set $S$ in a graph $G = (V, E)$ is an independent set of vertices such that, for every vertex $v \in V ∖ S$ , either $N (v) \cap S = \emptyset$ or $|N(v) \cap…

math.CO2025

Nordhaus-Gaddum-type theorems for maximum average degree

Yair Caro, Zsolt Tuza

A $k$ -decomposition $(G_{1}, \dots, G_{k})$ of a graph $G$ is a partition of its edge set into $k$ spanning subgraphs $G_{1}, \dots, G_{k}$ . The classical theorem of Nordhaus and Gaddum bounds…

math.CO2025

Bipartite Turán number of trees

Yair Caro, Balázs Patkós, Zsolt Tuza

We start a systematic investigation concerning bipartite Turán number for trees. For a graph $F$ and integers $1 \leq a \leq b$ we define: $(i)$ \quad $e x_{b} (a, b, F)$ is the largest…

math.CO2025

Monochromatic graph decompositions and monochromatic piercing inspired by anti-Ramsey colorings

Yair Caro, Zsolt Tuza

Anti-Ramsey theory was initiated in 1975 by Erdős, Simonovits and Sós, inspiring hundreds of publications since then. The present work is the third and last piece of our trilogy in…

math.CO2024

Open problems of the 32nd Workshop on Cycles and Colourings

János Barát, Stijn Cambie, Geňa Hahn +4

Since its beginnings, every Cycles and Colourings workshop holds one or two open problem sessions; this document contains the problems (together with notes regarding the current st…

math.CO2024

On strong odd colorings of graphs

Yair Caro, Mirko Petruševski, Riste Škrekovski +1

A strong odd coloring of a simple graph $G$ is a proper coloring of the vertices of $G$ such that for every vertex $v$ and every color $c$ , either $c$ is used an odd number of time…

math.CO2024

Graphs with constant links and induced Turán numbers

Yair Caro, Adriana Hansberg, Zsolt Tuza

A graph $G$ of constant link $L$ is a graph in which the neighborhood of any vertex induces a graph isomorphic to $L$ . Given two different graphs, $H$ and $G$ , the induced Turán nu…

math.CO2024

An exploration of the balance game

Paul Dorbec, Michael A. Henning, Zsolt Tuza +1

The balance game is played on a graph $G$ by two players, Admirable (A) and Impish (I), who take turns selecting unlabeled vertices of $G$ . Admirable labels the selected vertices b…

math.CO2024★ 1 cited

Monochromatic graph decompositions inspired by anti-Ramsey theory and the odd-coloring problem

Yair Caro, Zsolt Tuza

We consider extremal edge-coloring problems inspired by the theory of anti-Ramsey / rainbow coloring, and further by odd-colorings and conflict-free colorings. Let $G$ be a graph,…

math.CO2024

Monochromatic graph decompositions inspired by anti-Ramsey colorings

Yair Caro, Zsolt Tuza

We consider coloring problems inspired by the theory of anti-Ramsey / rainbow colorings that we generalize to a far extent. Let $F$ be a hereditary family of graphs; i.e.…

math.CO2023

Indicated domination game

Boštjan Brešar, Csilla Bujtás, Vesna Iršič +2

Motivated by the success of domination games and by a variation of the coloring game called the indicated coloring game, we introduce a version of domination games called the indic…

math.CO2023

The robust chromatic number of certain graph classes

Gábor Bacsó, Csilla Bujtás, Balázs Patkós +2

A 1-selection $f$ of a graph $G$ is a function $f : V (G) \to E (G)$ such that $f (v)$ is incident to $v$ for every vertex $v$ . The 1-removed $G_{f}$ is the graph $(V(G),E(G)\setm…

math.CO2023

The robust chromatic number of graphs

Gábor Bacsó, Balázs Patkós, Zsolt Tuza +1

A 1-removed subgraph $G_{f}$ of a graph $G = (V, E)$ is obtained by $(i)$ selecting at most one edge $f (v)$ for each vertex $v \in V$ , such that $v \in f (v) \in E$ (the mapping $f:V\to E \…

math.CO2023

Extremal graph theoretic questions for q-ary vectors

Balázs Patkós, Zsolt Tuza, Máté Vizer

A $q$ -graph $H$ on $n$ vertices is a set of vectors of length $n$ with all entries from ${0, 1, \dots, q}$ and every vector (that we call a $q$ -edge) having exactly two non-zero ent…

math.CO2023

Vector sum-intersection theorems

Balázs Patkós, Zsolt Tuza, Máté Vizer

We introduce the following generalization of set intersection via characteristic vectors: for $n, q, s, t \geq 1$ a family $F \subseteq {0, 1, \dots, q}^{n}$ of vectors is said…

math.CO2022

Spectrum of $3$ -uniform $6$ - and $9$ -cycle systems over $K_{v}^{(3)} - I$

Anita Keszler, Zsolt Tuza

We consider edge decompositions of $K_{v}^{(3)} - I$ , the complete 3-uniform hypergraph of order $v$ minus a 1-factor (parallel class, packing of $v /3$ disjoint edges). We prove that a…

math.CO2022

Counting Connected Partitions of Graphs

Yair Caro, Balázs Patkós, Zsolt Tuza +1

Motivated by the theorem of Gy\H ori and Lovász, we consider the following problem. For a connected graph $G$ on $n$ vertices and $m$ edges determine the number $P (G, k)$ of unorder…

math.CO2022★ 1 cited

Connected Turán number of trees

Yair Caro, Balázs Patkós, Zsolt Tuza

As a variant of the much studied Turán number, $e x (n, F)$ , the largest number of edges that an $n$ -vertex $F$ -free graph may contain, we introduce the connected Turán number $ex_c(n…

math.CO2021

Strong edge coloring of Cayley graphs and some product graphs

Suresh Dara, Suchismita Mishra, Narayanan Narayanan +1

A strong edge coloring of a graph $G$ is a proper edge coloring of $G$ such that every color class is an induced matching. The minimum number of colors required is termed the stron…

math.CO2021

Optimal strategies in fractional games: vertex cover and domination

Csilla Bujtás, Günter Rote, Zsolt Tuza

In a hypergraph with vertex set $V$ and edge set $E$ , a real-valued function $f : V \to [0, 1]$ is a fractional transversal if $\sum_{v \in e} f (v) \geq 1$ for every edge $e \in E$ . I…

math.CO2021

The k-path vertex cover: general bounds and chordal graphs

Csilla Bujtás, Marko Jakovac, Zsolt Tuza

For an integer $k \geq 3$ , a $k$ -path vertex cover of a graph $G = (V, E)$ is a set $T \subseteq V$ that shares a vertex with every path subgraph of order $k$ in $G$ . The minimum cardina…

The strong (non-induced) Turán numbers

Induced/Incomparable versus Ramsey

The odd independence number of graphs, II: Finite and infinite grids and chessboard graphs

The odd independence number of graphs, I: Foundations and classical classes

Nordhaus-Gaddum-type theorems for maximum average degree

Bipartite Turán number of trees

Monochromatic graph decompositions and monochromatic piercing inspired by anti-Ramsey colorings

Open problems of the 32nd Workshop on Cycles and Colourings

On strong odd colorings of graphs

Graphs with constant links and induced Turán numbers

An exploration of the balance game

Monochromatic graph decompositions inspired by anti-Ramsey theory and the odd-coloring problem

Monochromatic graph decompositions inspired by anti-Ramsey colorings

Indicated domination game

The robust chromatic number of certain graph classes

The robust chromatic number of graphs

Extremal graph theoretic questions for q-ary vectors

Vector sum-intersection theorems

Spectrum of 3-uniform 6- and 9-cycle systems over Kv(3)​−I

Counting Connected Partitions of Graphs

Connected Turán number of trees

Strong edge coloring of Cayley graphs and some product graphs

Optimal strategies in fractional games: vertex cover and domination

The k-path vertex cover: general bounds and chordal graphs

Spectrum of $3$ -uniform $6$ - and $9$ -cycle systems over $K_{v}^{(3)} - I$