Zobrazeno 1 - 10
of 653
pro vyhledávání: '"Dvorák, Zdenek"'
Through computer-assisted enumeration, we list minimal obstructions for 5-choosability of graphs on the torus with the following additional property: There exists a cyclic system of non-contractible triangles around the torus where the consecutive tr
Externí odkaz:
http://arxiv.org/abs/2407.18800
Autor:
Dvořák, Zdeněk, Norin, Sergey
A connected graph G is 3-flow-critical if G does not have a nowhere-zero 3-flow, but every proper contraction of G does. We prove that every n-vertex 3-flow-critical graph other than K_2 and K_4 has at least 5n/3 edges. This bound is tight up to lowe
Externí odkaz:
http://arxiv.org/abs/2404.00324
We consider the 4-precoloring extension problem in \emph{planar near-Eulerian-triangulations}, i.e., plane graphs where all faces except possibly for the outer one have length three, all vertices not incident with the outer face have even degree, and
Externí odkaz:
http://arxiv.org/abs/2312.13061
Autor:
Dvořák, Zdeněk, Feghali, Carl
We show that $\limsup |E(G)|/|V(G)| = 2.5$ over all $4$-critical planar graphs $G$, answering a question of Gr\"unbaum from 1988.
Comment: 14 pages, 7 figures
Comment: 14 pages, 7 figures
Externí odkaz:
http://arxiv.org/abs/2311.03132
Autor:
Dvorak, Zdenek, Yepremyan, Liana
We show that Erd\H{o}s-R\'enyi random graphs $G(n,p)$ with constant density $p<1$ have correspondence chromatic number $O(n/\sqrt{\log n})$; this matches a prediction from linear Hadwiger's conjecture for correspondence coloring. The proof follows fr
Externí odkaz:
http://arxiv.org/abs/2307.15048
Autor:
Dvořák, Zdeněk, Lahiri, Abhiruk
The maximum edge colouring problem considers the maximum colour assignment to edges of a graph under the condition that every vertex has at most a fixed number of distinct coloured edges incident on it. If that fixed number is $q$ we call the colouri
Externí odkaz:
http://arxiv.org/abs/2307.02314
Autor:
Dvořák, Zdeněk
Esperet and Joret proved that planar graphs with bounded maximum degree are 3-colorable with bounded clustering. Liu and Wood asked whether the conclusion holds with the assumption of the bounded maximum degree replaced by assuming that no two vertic
Externí odkaz:
http://arxiv.org/abs/2306.09834
We investigate a fundamental vertex-deletion problem called (Induced) Subgraph Hitting: given a graph $G$ and a set $\mathcal{F}$ of forbidden graphs, the goal is to compute a minimum-sized set $S$ of vertices of $G$ such that $G-S$ does not contain
Externí odkaz:
http://arxiv.org/abs/2304.13695
Autor:
Dvořák, Zdeněk
Let $\pi$ be a property of pairs $(G,Z)$, where $G$ is a graph and $Z\subseteq V(G)$. In the \emph{minimum $\pi$-hitting set problem}, given an input graph $G$, we want to find a smallest set $X\subseteq V(G)$ such that $X$ intersects every set $Z\su
Externí odkaz:
http://arxiv.org/abs/2304.12789
A graph drawn in a surface is a near-quadrangulation if the sum of the lengths of the faces different from 4-faces is bounded by a fixed constant. We leverage duality between colorings and flows to design an efficient algorithm for 3-precoloring-exte
Externí odkaz:
http://arxiv.org/abs/2303.05583