Zobrazeno 1 - 10
of 37
pro vyhledávání: '"Rambaud, Clément"'
A vertex coloring $\varphi$ of a graph $G$ is $p$-centered if for every connected subgraph $H$ of $G$, either $\varphi$ uses more than $p$ colors on $H$, or there is a color that appears exactly once on $H$. We prove that for every fixed positive int
Externí odkaz:
http://arxiv.org/abs/2411.02122
Autor:
Aboulker, Pierre, Havet, Frédéric, Lochet, William, Lopes, Raul, Picasarri-Arrieta, Lucas, Rambaud, Clément
A class of acyclic digraphs $\mathscr{C}$ is linearly unavoidable if there exists a constant $c$ such that every digraph $D\in \mathscr{C}$ is contained in all tournaments of order $c\cdot |V(D)|$. The class of all acyclic digraphs is not linearly av
Externí odkaz:
http://arxiv.org/abs/2410.23566
We study the growth rate of weak coloring numbers of graphs excluding a fixed graph as a minor. Van den Heuvel et al. (European J. of Combinatorics, 2017) showed that for a fixed graph $X$, the maximum $r$-th weak coloring number of $X$-minor-free gr
Externí odkaz:
http://arxiv.org/abs/2407.04588
In an oriented graph $\vec{G}$, the inversion of a subset $X$ of vertices consists in reversing the orientation of all arcs with both endvertices in $X$. The inversion graph of a labelled graph $G$, denoted by ${\mathcal{I}}(G)$, is the graph whose v
Externí odkaz:
http://arxiv.org/abs/2405.04119
We give a short proof that for every apex-forest $X$ on at least two vertices, graphs excluding $X$ as a minor have layered pathwidth at most $2|V(X)|-3$. This improves upon a result by Dujmovi\'c, Eppstein, Joret, Morin, and Wood (SIDMA, 2020). Our
Externí odkaz:
http://arxiv.org/abs/2404.17306
We show that the vertices of every planar graph can be partitioned into two sets, each inducing a so-called triangle-forest, i.e., a graph with no cycles of length more than three. We further discuss extensions to locally planar graphs. After finishi
Externí odkaz:
http://arxiv.org/abs/2401.15394
Aboulker et al. proved that a digraph with large enough dichromatic number contains any fixed digraph as a subdivision. The dichromatic number of a digraph is the smallest order of a partition of its vertex set into acyclic induced subdigraphs. A dig
Externí odkaz:
http://arxiv.org/abs/2401.05938
Autor:
Duraj, Lech, Kang, Ross J., La, Hoang, Narboni, Jonathan, Pokrývka, Filip, Rambaud, Clément, Reinald, Amadeus
Given a positive integer $d$, the class $d$-DIR is defined as all those intersection graphs formed from a finite collection of line segments in ${\mathbb R}^2$ having at most $d$ slopes. Since each slope induces an interval graph, it easily follows f
Externí odkaz:
http://arxiv.org/abs/2309.06072
Autor:
Dujmović, Vida, Hickingbotham, Robert, Hodor, Jędrzej, Joret, Gweanël, La, Hoang, Micek, Piotr, Morin, Pat, Rambaud, Clément, Wood, David R.
We prove that for every planar graph $X$ of treedepth $h$, there exists a positive integer $c$ such that for every $X$-minor-free graph $G$, there exists a graph $H$ of treewidth at most $f(h)$ such that $G$ is isomorphic to a subgraph of $H\boxtimes
Externí odkaz:
http://arxiv.org/abs/2307.02816
The dichromatic number $\vec{\chi}(D)$ of a digraph $D$ is the minimum number of colours needed to colour the vertices of a digraph such that each colour class induces an acyclic subdigraph. A digraph $D$ is $k$-dicritical if $\vec{\chi}(D) = k$ and
Externí odkaz:
http://arxiv.org/abs/2306.10784