Zobrazeno 1 - 10
of 30
pro vyhledávání: '"Pierre Charbit"'
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol Vol. 16 no. 2, Iss PRIMA 2013 (2014)
End-vertices of a given graph search may have some nice properties, as for example it is well known that the last vertex of Lexicographic Breadth First Search (LBFS) in a chordal graph is simplicial, see Rose, Tarjan and Lueker 1976. Therefore it is
Externí odkaz:
https://doaj.org/article/e63918b045654baca281724f2d8081c2
Autor:
Rezvan Sherkati, Manuel Lafond, Ben Seamone, Marcin Kamiński, Nicolas Lichiardopol, Geňa Hahn, Pierre Charbit, Reza Naserasr
Publikováno v:
Journal of Graph Theory. 97:324-339
The edge clique cover number ecc(G) of a graph G is size of the smallest collection of complete sub-graphs whose union covers all edges of G. Chen, Jacobson, Kezdy, Lehel, Scheinerman, and Wang conjectured in 2000 that if G is claw-free, then ecc(G)
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::1a05294734cfce9e69c7cd4ee47de5fc
https://doi.org/10.1002/jgt.22657
https://doi.org/10.1002/jgt.22657
Autor:
Paweł Rzążewski, Panos Giannopoulos, Marthe Bonamy, Stéphan Thomassé, Nicolas Bousquet, Édouard Bonnet, Pierre Charbit, Florian Sikora, Eun Jung Kim
Publikováno v:
Journal of the ACM (JACM)
Journal of the ACM (JACM), Association for Computing Machinery, 2021, 68 (2), pp.1-38. ⟨10.1145/3433160⟩
Journal of the ACM (JACM), 2021, 68 (2), pp.1-38. ⟨10.1145/3433160⟩
Journal of the ACM
Journal of the ACM (JACM), Association for Computing Machinery, 2021, 68 (2), pp.1-38. ⟨10.1145/3433160⟩
Journal of the ACM (JACM), 2021, 68 (2), pp.1-38. ⟨10.1145/3433160⟩
Journal of the ACM
A (unit) disk graph is the intersection graph of closed (unit) disks in the plane. Almost three decades ago, an elegant polynomial-time algorithm was found for \textsc{Maximum Clique} on unit disk graphs [Clark, Colbourn, Johnson; Discrete Mathematic
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::08e7270d7f539eeb78e1d4fabec534de
https://hal.archives-ouvertes.fr/hal-03107441
https://hal.archives-ouvertes.fr/hal-03107441
Publikováno v:
Trends in Mathematics ISBN: 9783030838225
We study the dichromatic number of a digraph, defined as the minimum number of parts in a partition of its vertex set into acyclic induced subdigraphs. We consider the class of oriented graphs such that the out-neighbourhood of any vertex induces a t
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::a047ba1c402a2e3a0314a0be78d8d78d
https://doi.org/10.1007/978-3-030-83823-2_110
https://doi.org/10.1007/978-3-030-83823-2_110
Publikováno v:
The Electronic Journal of Combinatorics
The Electronic Journal of Combinatorics, Open Journal Systems, 2021, ⟨10.37236/9906⟩
The Electronic Journal of Combinatorics, 2021, ⟨10.37236/9906⟩
The Electronic Journal of Combinatorics, Open Journal Systems, 2021, ⟨10.37236/9906⟩
The Electronic Journal of Combinatorics, 2021, ⟨10.37236/9906⟩
The dichromatic number of a digraph $D$ is the minimum number of colors needed to color its vertices in such a way that each color class induces an acyclic digraph. As it generalizes the notion of the chromatic number of graphs, it has been a recent
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::dfa6441fe824c856c969fe4d5d7f7f24
http://arxiv.org/abs/2009.13319
http://arxiv.org/abs/2009.13319
Publikováno v:
Discrete Mathematics
Discrete Mathematics, Elsevier, 2019, 342 (8), pp.2195-2203. ⟨10.1016/j.disc.2019.04.021⟩
Discrete Mathematics, 2019, 342 (8), pp.2195-2203. ⟨10.1016/j.disc.2019.04.021⟩
Discrete Mathematics, Elsevier, 2019, 342 (8), pp.2195-2203. ⟨10.1016/j.disc.2019.04.021⟩
Discrete Mathematics, 2019, 342 (8), pp.2195-2203. ⟨10.1016/j.disc.2019.04.021⟩
A decomposition of a multigraph $G$ is a partition of its edges into subgraphs $G(1), \ldots , G(k)$. It is called an $r$-factorization if every $G(i)$ is $r$-regular and spanning. If $G$ is a subgraph of $H$, a decomposition of $G$ is said to be enc
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::34d241d432e63dcc5041d2df61658547
https://hal.inria.fr/hal-02429274
https://hal.inria.fr/hal-02429274
Autor:
Oscar Defrain, Jean-Sébastien Sereni, Pierre Charbit, Aurélie Lagoutte, Lucas Pastor, Marthe Bonamy, Gwenaël Joret, Vincent Limouzy
Publikováno v:
The electronic journal of combinatorics, 27 (1
The Electronic Journal of Combinatorics
The Electronic Journal of Combinatorics, Open Journal Systems, 2020, 27 (1), pp.P1.56. ⟨10.37236/8899⟩
The Electronic Journal of Combinatorics, 2020, 27 (1), pp.P1.56. ⟨10.37236/8899⟩
The Electronic Journal of Combinatorics
The Electronic Journal of Combinatorics, Open Journal Systems, 2020, 27 (1), pp.P1.56. ⟨10.37236/8899⟩
The Electronic Journal of Combinatorics, 2020, 27 (1), pp.P1.56. ⟨10.37236/8899⟩
We give a short proof of the following theorem due to Jon H. Folkman (1969): The chromatic number of any graph is at most 2 plus the maximum over all subgraphs of the difference between the number of vertices and twice the independence number.
S
S
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3f819feba2ca2b69090ca69dd4557d24
https://hal.archives-ouvertes.fr/hal-02194900
https://hal.archives-ouvertes.fr/hal-02194900
Publikováno v:
IPEC 2018-13th International Symposium on Parameterized and Exact Computation
IPEC 2018-13th International Symposium on Parameterized and Exact Computation, Aug 2018, Helsinki, Finland. ⟨10.4230/LIPIcs.CVIT.2016.23⟩
Algorithmica
Algorithmica, Springer Verlag, 2020, 82 (8), pp.2360-2394. ⟨10.1007/s00453-020-00730-6⟩
Algorithmica, Springer Verlag, 2020, Parameterized and Exact Computation, IPEC 2018, 82 (8), pp.2360-2394. ⟨10.1007/s00453-020-00730-6⟩
Algorithmica, 2020, Parameterized and Exact Computation, IPEC 2018, 82 (8), pp.2360-2394. ⟨10.1007/s00453-020-00730-6⟩
IPEC 2018-13th International Symposium on Parameterized and Exact Computation, Aug 2018, Helsinki, Finland. ⟨10.4230/LIPIcs.CVIT.2016.23⟩
Algorithmica
Algorithmica, Springer Verlag, 2020, 82 (8), pp.2360-2394. ⟨10.1007/s00453-020-00730-6⟩
Algorithmica, Springer Verlag, 2020, Parameterized and Exact Computation, IPEC 2018, 82 (8), pp.2360-2394. ⟨10.1007/s00453-020-00730-6⟩
Algorithmica, 2020, Parameterized and Exact Computation, IPEC 2018, 82 (8), pp.2360-2394. ⟨10.1007/s00453-020-00730-6⟩
In this paper, we investigate the complexity of Maximum Independent Set (MIS) in the class of $H$-free graphs, that is, graphs excluding a fixed graph as an induced subgraph. Given that the problem remains $NP$-hard for most graphs $H$, we study its
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::f6a60a7ad730e8b4bd467d2fb9aae78c
http://arxiv.org/abs/1810.04620
http://arxiv.org/abs/1810.04620
Publikováno v:
59th Annual IEEE Symposium on Foundations of Computer Science
FOCS: Foundations of Computer Science
FOCS: Foundations of Computer Science, Oct 2018, Paris, France. ⟨10.1109/FOCS.2018.00060⟩
FOCS: Foundations of Computer Science, Oct 2018, Paris, France. ⟨10.4230/LIPIcs⟩
FOCS: Foundations of Computer Science
FOCS: Foundations of Computer Science, Oct 2018, Paris, France. ⟨10.1109/FOCS.2018.00060⟩
FOCS: Foundations of Computer Science, Oct 2018, Paris, France. ⟨10.4230/LIPIcs⟩
We propose a polynomial-time algorithm which takes as input a finite set of points of $\mathbb R^3$ and compute, up to arbitrary precision, a maximum subset with diameter at most $1$. More precisely, we give the first randomized EPTAS and determinist
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ae1a9fc8b4caec2f0531d8f873bbe55a
https://inria.hal.science/hal-01962198
https://inria.hal.science/hal-01962198
Autor:
Pierre Charbit, Frédéric Maffray, Nicolas Bousquet, Frédéric Havet, José Zamora, Jørgen Bang-Jensen, Pierre Aboulker
Publikováno v:
Journal of Graph Theory
Journal of Graph Theory, Wiley, 2018, 89 (3), pp.304-326. ⟨10.1002/jgt.22252⟩
Aboulker, P, Bang-Jensen, J, Bousquet, N, Charbit, P, Havet, F, Maffray, F & Zamora, J 2018, ' χ-bounded families of oriented graphs ', Journal of Graph Theory, vol. 89, no. 3, pp. 304-326 . https://doi.org/10.1002/jgt.22252
Journal of Graph Theory, 2018, 89 (3), pp.304-326. ⟨10.1002/jgt.22252⟩
Journal of Graph Theory, Wiley, 2018, 89 (3), pp.304-326. ⟨10.1002/jgt.22252⟩
Aboulker, P, Bang-Jensen, J, Bousquet, N, Charbit, P, Havet, F, Maffray, F & Zamora, J 2018, ' χ-bounded families of oriented graphs ', Journal of Graph Theory, vol. 89, no. 3, pp. 304-326 . https://doi.org/10.1002/jgt.22252
Journal of Graph Theory, 2018, 89 (3), pp.304-326. ⟨10.1002/jgt.22252⟩
A famous conjecture of Gy\'arf\'as and Sumner states for any tree $T$ and integer $k$, if the chromatic number of a graph is large enough, either the graph contains a clique of size $k$ or it contains $T$ as an induced subgraph. We discuss some resul
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d5f640969b16f88853de63cba08f9020
https://hal.inria.fr/hal-01882395/file/Induced-digraphs-revised.pdf
https://hal.inria.fr/hal-01882395/file/Induced-digraphs-revised.pdf