Examinando por Autor "Aboulker, Pierre"
Mostrando 1 - 3 de 3
Resultados por página
Opciones de ordenación
Ítem Coloring Graphs with Constraints on Connectivity(Wiley-Liss Inc., 2017-08) Aboulker, Pierre; Brettell, Nick; Havet, Frédéric; Marx, Dániel; Trotignon, NicolasA graph G has maximal local edge-connectivity k if the maximum number of edge-disjoint paths between every pair of distinct vertices x and y is at most k. We prove Brooks-type theorems for k-connected graphs with maximal local edge-connectivity k, and for any graph with maximal local edge-connectivity 3. We also consider several related graph classes defined by constraints on connectivity. In particular, we show that there is a polynomial-time algorithm that, given a 3-connected graph G with maximal local connectivity 3, outputs an optimal coloring for G. On the other hand, we prove, for k≥3, that k-colorability is NP-complete when restricted to minimally k-connected graphs, and 3-colorability is NP-complete when restricted to (k − 3) -connected graphs with maximal local connectivity k. Finally, we consider a parameterization of k-colorability based on the number of vertices of degree at least k + 1, and prove that, even when k is part of the input, the corresponding parameterized problem is FPT. © 2016 Wiley Periodicals, Inc.Ítem De Bruijn–Erdős-type theorems for graphs and posets(Elsevier B.V., 2017-05) Aboulker, Pierre; Lagarde, Guillaume; Malec, David; Methuku, Abhishek; Tompkins, CaseyA classical theorem of De Bruijn and Erdős asserts that any noncollinear set of n points in the plane determines at least n distinct lines. We prove that an analogue of this theorem holds for posets, where lines are defined using the natural betweenness relation in posets. More precisely, we obtain a bound on the number of lines depending on the height of the poset. The extremal configurations are also determined. Finally, we introduce a new notion of lines in graphs and show that our result for posets can be extended to this setting. © 2017 Elsevier B.V.Ítem Wheel-free planar graphs(Academic Press, 2015-10) Aboulker, Pierre; Chudnovsky, Maria; Seymour, Paul; Trotignon, NicolasA wheel is a graph formed by a chordless cycle C and a vertex u not in C that has at least three neighbors in C. We prove that every 3-connected planar graph that does not contain a wheel as an induced subgraph is either a line graph or has a clique cutset. We prove that every planar graph that does not contain a wheel as an induced subgraph is 3-colorable. © 2015 Elsevier Ltd.