Marcin Brianski

activity

20202025

collaborators

Showing math.COShow all

6 papers · 1 filter

math.CO2024

Erdős-Pósa property of tripods in directed graphs

Marcin Briański, Meike Hatzel, Karolina Okrasa +1

Let $D$ be a directed graphs with distinguished sets of sources $S \subseteq V (D)$ and sinks $T \subseteq V (D)$ . A tripod in $D$ is a subgraph consisting of the union of two $S$ - $T$ -…

math.CO2024★ 1 cited

Excluding a clique or a biclique in graphs of bounded induced matching treewidth

Tara Abrishami, Marcin Briański, Jadwiga Czyżewska +4

For a tree decomposition $T$ of a graph $G$ , let $μ (T)$ denote the maximum size of an induced matching in $G$ with the property that some bag of $T$ c…

math.CO2024

Defective and Clustered Colouring of Graphs with Given Girth

Marcin Briański, Robert Hickingbotham, David R. Wood

The defective chromatic number of a graph class $G$ is the minimum integer $k$ such that for some integer $d$ , every graph in $G$ is $k$ -colourable such that ea…

math.CO2023

Boolean dimension of a Boolean lattice

Marcin Briański, Jędrzej Hodor, Hoang La +2

For every integer $n$ with $n \geq 6$ , we prove that the Boolean dimension of a poset consisting of all the subsets of ${1, \dots, n}$ equipped with the inclusion relation is stric…

math.CO2021

Reconfiguring Independent Sets on Interval Graphs

Marcin Briański, Stefan Felsner, Jędrzej Hodor +1

We study reconfiguration of independent sets in interval graphs under the token sliding rule. We show that if two independent sets of size $k$ are reconfigurable in an $n$ -vertex i…

math.CO2020

Erdős-Hajnal properties for powers of sparse graphs

Marcin Briański, Piotr Micek, Michał Pilipczuk +1

We prove that for every nowhere dense class of graphs $C$ , positive integer $d$ , and $ε > 0$ , the following holds: in every $n$ -vertex graph $G$ from $\mathcal{C}…