Zobrazeno 1 - 10
of 44
pro vyhledávání: '"BRIAŃSKI, MARCIN"'
Negami's famous planar cover conjecture is equivalent to the statement that a connected graph can be embedded in the projective plane if and only if it has a projective planar cover. In 1999, Hlin\v{e}n\'y proposed extending this conjecture to higher
Externí odkaz:
http://arxiv.org/abs/2412.04420
Hutchinson, Richter and Seymour [J. Combin. Theory Ser. B 84 (2002), 225-239] showed that every Eulerian triangulation of an orientable surface that has a sufficiently high representativity is 4-colorable. We give an explicit bound on the representat
Externí odkaz:
http://arxiv.org/abs/2409.19165
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$-paths that have distinct start-vertices and the same end-vertex, and a
Externí odkaz:
http://arxiv.org/abs/2408.16733
Autor:
Abrishami, Tara, Briański, Marcin, Czyżewska, Jadwiga, McCarty, Rose, Milanič, Martin, Rzążewski, Paweł, Walczak, Bartosz
For a tree decomposition $\mathcal{T}$ of a graph $G$, let $\mu(\mathcal{T})$ denote the maximum size of an induced matching in $G$ with the property that some bag of $\mathcal{T}$ contains at least one endpoint of every edge of the matching. The ind
Externí odkaz:
http://arxiv.org/abs/2405.04617
The defective chromatic number of a graph class $\mathcal{G}$ is the minimum integer $k$ such that for some integer $d$, every graph in $\mathcal{G}$ is $k$-colourable such that each monochromatic component has maximum degree at most $d$. Similarly,
Externí odkaz:
http://arxiv.org/abs/2404.14940
The notion of branch-depth for matroids was introduced by DeVos, Kwon and Oum as the matroid analogue of the tree-depth of graphs. The contraction-deletion-depth, another tree-depth like parameter of matroids, is the number of recursive steps needed
Externí odkaz:
http://arxiv.org/abs/2402.16215
The contraction$^*$-depth is the matroid depth parameter analogous to tree-depth of graphs. We establish the matroid analogue of the classical graph theory result asserting that the tree-depth of a graph $G$ is the minimum height of a rooted forest w
Externí odkaz:
http://arxiv.org/abs/2311.01945
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 strictly less than $n$.
Externí odkaz:
http://arxiv.org/abs/2307.16671
Publikováno v:
SIAM Journal on Discrete Mathematics, 38/1:857-866, 2024
The {\em circumference} of a graph $G$ with at least one cycle is the length of a longest cycle in $G$. A classic result of Birmel\'e (2003) states that the treewidth of $G$ is at most its circumference minus $1$. In case $G$ is $2$-connected, this u
Externí odkaz:
http://arxiv.org/abs/2306.03621
Autor:
Briański, Marcin, Joret, Gwenaël, Majewski, Konrad, Micek, Piotr, Seweryn, Michał T., Sharma, Roohani
Publikováno v:
Combinatorica, 43:659--664, 2023
The circumference of a graph $G$ is the length of a longest cycle in $G$, or $+\infty$ if $G$ has no cycle. Birmel\'e (2003) showed that the treewidth of a graph $G$ is at most its circumference minus $1$. We strengthen this result for $2$-connected
Externí odkaz:
http://arxiv.org/abs/2211.11410