J. Makowsky

collaborators

4 papers

cs.LO2026

Extensions of Courcelle's Theorem without Logic

Yuval Filmus, Johann A. Makowsky

Courcelle's Theorem states that on graphs $G$ of tree-width at most $k$ with a given tree-decomposition of size $t (G)$ , graph properties $P$ definable in Monadic Second O…

math.CO2025

Distinctive power and comparability of Harary polynomial

Johann A. Makowsky

Let $P$ be a graph property. A $P$ -coloring with at most $k$ colors is a coloring of the vertices of a simple graph $G$ such that each color class induces a gra…

cs.LO2025

Courcelle's Theorem Without Logic

Yuval Filmus, Johann A. Makowsky

Courcelle's Theorem states that on graphs $G$ of tree-width at most $k$ with a given tree-decomposition of size $t (G)$ , graph properties $P$ definable in Monadic Second O…

math.CO2025

Effective MC-finiteness

Yuval Filmus, Eldar Fischer, Johann A. Makowsky

An integer sequence $(a_{n})_{n \in N}$ is \emph{MC-finite} if for all $m$ , the sequence $a_{n} mod m$ is eventually periodic. There are MC-finite sequences $(a_n)_{n \in \m…