Marco Caoduro

activity

20212026

most citedLower bound for constant-size local certification

1 citations · 1 across the 10 of their papers we have counts for

collaborators

10 papers

math.CO2026

Boxicity and Threshold Dimension of Zero Divisor Graphs

Marco Caoduro, Meike Neuwohner

The zero divisor graph $Γ (R)$ of a finite commutative ring $R$ has as vertices the non-zero zero divisors of $R$ , with an edge between two elements exactly when their product is ze…

math.CO2025

A polynomial algorithm to compute the boxicity and threshold dimension of complements of block graphs

Marco Caoduro, Will Evans, Tao Gaede

The boxicity of a graph $G$ is the minimum dimension $d$ that admits a representation of $G$ as the intersection graph of a family of axis-parallel boxes in $R^{d}$ . Computi…

math.CO2025

On the Boxicity of Line Graphs and of Their Complements

Marco Caoduro, András Sebő

The boxicity of a graph is the smallest dimension $d$ allowing a representation of it as the intersection graph of a set of $d$ -dimensional axis-parallel boxes. We present a simple…

math.CO2024

Characterizing unimodular laminar hypergraphs via forbidden subhypergraphs

Marco Caoduro, Meike Neuwohner, Joseph Paat

The incidence matrix of a graph is totally unimodular if and only if the graph is bipartite, i.e., it contains no odd cycles. We extend the characterization of total unimodularity…

math.CO2023

Boxicity and Interval-Orders: Petersen and the Complements of Line Graphs

Marco Caoduro, András Sebő

The boxicity of a graph is the smallest dimension $d$ allowing a representation of it as the intersection graph of a set of $d$ -dimensional axis-parallel boxes. We present a simple…

cs.DC2022★ 1 cited

Lower bound for constant-size local certification

Virgina Ardévol Martínez, Marco Caoduro, Laurent Feuilloley +3

Given a network property or a data structure, a local certification is a labeling that allows to efficiently check that the property is satisfied, or that the structure is correct.…

cs.CG2022

Packing, Hitting, and Colouring Squares

Marco Caoduro, András Sebő

Given a finite family of squares in the plane, the packing problem asks for the maximum number $ν$ of pairwise disjoint squares among them, while the hitting problem for the minimu…

math.CO2022

Independence number of intersection graphs of axis-parallel segments

Marco Caoduro, Jana Cslovjecsek, Michał Pilipczuk +1

We prove that for any triangle-free intersection graph of $n$ axis-parallel segments in the plane, the independence number $α$ of this graph is at least $α \geq n /4 + Ω (n)$ . W…

math.CO2021

On the Boxicity of Kneser Graphs and Complements of Line Graphs

Marco Caoduro, Lyuben Lichev

An axis-parallel $d$ -dimensional box is a cartesian product $I_{1} \times I_{2} \times \dots \times I_{b}$ where $I_{i}$ is a closed sub-interval of the real line. For a graph $G = (V, E)$ , t…

math.CO2021

Packing and coloring r-bounded axis-parallel rectangles

Marco Caoduro

Let $R$ be a family of axis-parallel rectangles in the plane. The transversal number $τ (R)$ is the minimum number of points needed to pierce all the rectangles.…