Zobrazeno 1 - 10
of 79
pro vyhledávání: '"Gwenaël Joret"'
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol vol. 22 no. 4, Iss Graph Theory (2020)
Given a graph $G$ and an integer $p$, a coloring $f : V(G) \to \mathbb{N}$ is \emph{$p$-centered} if for every connected subgraph $H$ of $G$, either $f$ uses more than $p$ colors on $H$ or there is a color that appears exactly once in $H$. The notion
Externí odkaz:
https://doaj.org/article/e8bebe963e844d69aec12471b1824778
Autor:
Gwenaël Joret, Adrian Vetta
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol Vol. 17 no.2, Iss Discrete Algorithms (2015)
We consider the rank reduction problem for matroids: Given a matroid $M$ and an integer $k$, find a minimum size subset of elements of $M$ whose removal reduces the rank of $M$ by at least $k$. When $M$ is a graphical matroid this problem is the mini
Externí odkaz:
https://doaj.org/article/46237f9cc43240b1b46bad2599a7db5f
Publikováno v:
SIAM Journal on Discrete Mathematics; 2024, Vol. 38 Issue 1, p857-866, 10p
Publikováno v:
Combinatorica
A ladder is a $2 \times k$ grid graph. When does a graph class $\mathcal{C}$ exclude some ladder as a minor? We show that this is the case if and only if all graphs $G$ in $\mathcal{C}$ admit a proper vertex coloring with a bounded number of colors s
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b71fc8ee18d0a8c006fa1d32bb959e69
https://ruj.uj.edu.pl/xmlui/handle/item/307961
https://ruj.uj.edu.pl/xmlui/handle/item/307961
Publikováno v:
SIAM journal on discrete mathematics, 34 (3
We prove that a minor-closed class of graphs has bounded layered pathwidth if and only if some apex-forest is not in the class. This generalises a theorem of Robertson and Seymour, which says that a minor-closed class of graphs has bounded pathwidth
Publikováno v:
The electronic journal of combinatorics, 28 (3
The clique chromatic number of a graph is the minimum number of colours needed to colour its vertices so that no inclusion-wise maximal clique, which is not an isolated vertex, is monochromatic. We show that every graph of maximum degree ∆ has cliq
Publikováno v:
Discrete & computational geometry, 66 (1
Discrete & computational geometry
Discrete & computational geometry
A metric graph is a pair (G, d), where G is a graph and d: E(G) → R≥ 0 is a distance function. Let p∈ [1 ,∞] be fixed. An isometric embedding of the metric graph (G, d) in ℓpk=(Rk,dp) is a map ϕ: V(G) → Rk such that dp(ϕ(v) ,ϕ(w)) = d(
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5325f61cd8d1770b8663909dca4d2852
http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/326874
http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/326874
Autor:
Gerardo Berbeglia, Gwenaël Joret
Publikováno v:
EC
Proceedings-ACM conference on Economics and Computation, ACM EC '17
Algorithmica, 82 (4
Proceedings-ACM conference on Economics and Computation, ACM EC '17
Algorithmica, 82 (4
The assortment problem in revenue management is the problem of deciding which subset of products to offer to consumers in order to maximise revenue. A simple and natural strategy is to select the best assortment out of all those that are constructed
Publikováno v:
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA)
Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021
Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021
We describe a polynomial-time algorithm which, given a graph $G$ with treewidth $t$, approximates the pathwidth of $G$ to within a ratio of $O(t\sqrt{\log t})$. This is the first algorithm to achieve an $f(t)$-approximation for some function $f$. Our
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::eacd2be3b98008c66a220f9429e39349
https://doi.org/10.1137/1.9781611976465.117
https://doi.org/10.1137/1.9781611976465.117
Publikováno v:
2019-20 MATRIX Annals ISBN: 9783030624965
It was recently proved that every planar graph is a subgraph of the strongproduct of a path and a graph with bounded treewidth. This paper surveys generalisationsof this result for graphs on surfaces, minor-closed classes, various nonminor-closed cla
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::8de8723dd79c70a9ee1b1e2c69c5a2ad
https://doi.org/10.1007/978-3-030-62497-2_32
https://doi.org/10.1007/978-3-030-62497-2_32