Search

Your search keyword '"Nicolas Trotignon"' showing total 62 results
Start Over Author "Nicolas Trotignon"
62 results on '"Nicolas Trotignon"'

1. On rank-width of even-hole-free graphs

Author

Isolde Adler, Ngoc Khang Le, Haiko Müller, Marko Radovanović, Nicolas Trotignon, and Kristina Vušković

Subjects
computer science - discrete mathematics, mathematics - combinatorics, 05c85, g.2.2, Mathematics, QA1-939
Abstract

We present a class of (diamond, even hole)-free graphs with no clique cutset that has unbounded rank-width. In general, even-hole-free graphs have unbounded rank-width, because chordal graphs are even-hole-free. A.A. da Silva, A. Silva and C. Linhares-Sales (2010) showed that planar even-hole-free graphs have bounded rank-width, and N.K. Le (2016) showed that even-hole-free graphs with no star cutset have bounded rank-width. A natural question is to ask, whether even-hole-free graphs with no clique cutsets have bounded rank-width. Our result gives a negative answer. Hence we cannot apply Courcelle and Makowsky's meta-theorem which would provide efficient algorithms for a large number of problems, including the maximum independent set problem, whose complexity remains open for (diamond, even hole)-free graphs.

Published
2017
Full Text
View/download PDF

6. The (theta, wheel)-free graphs Part I: Only-prism and only-pyramid graphs

Author

Marko Radovanović, Nicolas Trotignon, Kristina Vušković, Emilie Diot, Modèles de calcul, Complexité, Combinatoire (MC2), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-École normale supérieure - Lyon (ENS Lyon)

Subjects
Optimization problem, 010102 general mathematics, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, Theoretical Computer Science, Combinatorics, Computational Theory and Mathematics, 010201 computation theory & mathematics, FOS: Mathematics, Mathematics - Combinatorics, 05C75, Discrete Mathematics and Combinatorics, Combinatorics (math.CO), Prism, 0101 mathematics, Recognition algorithm, Time complexity, Mathematics
Abstract

International audience; Truemper configurations are four types of graphs (namely thetas, wheels, prisms and pyramids) that play an important role in the proof of several decomposition theorems for hereditary graph classes. In this paper, we prove two structure theorems: one for graphs with no thetas, wheels and prisms as induced subgraphs, and one for graphs with no thetas, wheels and pyramids as induced subgraphs. A consequence is a polynomial time recognition algorithms for these two classes. In Part II of this series we generalize these results to graphs with no thetas and wheels as induced subgraphs, and in Parts III and IV, using the obtained structure, we solve several optimization problems for these graphs. AMS classification: 05C75

Published
2020

7. The (theta, wheel)-free graphs Part III: Cliques, stable sets and coloring

Author

Marko Radovanović, Kristina Vušković, Nicolas Trotignon, Modèles de calcul, Complexité, Combinatoire (MC2), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), ANR-10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon(2010), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-École normale supérieure - Lyon (ENS Lyon)

Subjects
010102 general mathematics, Induced subgraph, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, Theoretical Computer Science, Vertex (geometry), Combinatorics, Part iii, Computational Theory and Mathematics, Computer Science::Discrete Mathematics, 010201 computation theory & mathematics, Independent set, Bounded function, FOS: Mathematics, Mathematics - Combinatorics, Discrete Mathematics and Combinatorics, Combinatorics (math.CO), Chromatic scale, 0101 mathematics, Time complexity, Mathematics
Abstract

International audience; A hole in a graph is a chordless cycle of length at least 4. A theta is a graph formed by three paths between the same pair of distinct vertices so that the union of any two of the paths induces a hole. A wheel is a graph formed by a hole and a node that has at least 3 neighbors in the hole. In this series of papers we study the class of graphs that do not contain as an induced subgraph a theta nor a wheel. In Part II of the series we prove a decomposition theorem for this class, that uses clique cutsets and 2-joins, and consequently obtain a polynomial time recognition algorithm for the class. In this paper we further use this decomposition theorem to obtain polynomial time algorithms for maximum weight clique, maximum weight stable set and coloring problems. We also show that for a graph $G$ in the class, if its maximum clique size is $\omega$, then its chromatic number is bounded by max$\{\omega,3\}$, and that the class is 3-clique-colorable.

Published
2020

8. (Theta, triangle)‐free and (even hole, K4)‐free graphs. Part 2: Bounds on treewidth

Author

Nicolas Trotignon, Ni Luh Dewi Sintiari, Stéphan Thomassé, Marcin Pilipczuk, Modèles de calcul, Complexité, Combinatoire (MC2), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), University of Warsaw (UW), ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), ANR-10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon(2010), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-École normale supérieure - Lyon (ENS Lyon)

Subjects
FOS: Computer and information sciences, Even-hole-free graph, Discrete Mathematics (cs.DM), 010102 general mathematics, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Treewidth, Combinatorics, 010201 computation theory & mathematics, Computer Science::Discrete Mathematics, Independent set, FOS: Mathematics, Mathematics - Combinatorics, Discrete Mathematics and Combinatorics, Geometry and Topology, Combinatorics (math.CO), 0101 mathematics, Computer Science - Discrete Mathematics, Mathematics
Abstract

International audience; A {\em theta} is a graph made of three internally vertex-disjoint chordless paths $P_1 = a \dots b$, $P_2 = a \dots b$, $P_3 = a \dots b$ of length at least~2 and such that no edges exist between the paths except the three edges incident to $a$ and the three edges incident to $b$. A {\em pyramid} is a graph made of three chordless paths $P_1 = a \dots b_1$, $P_2 = a \dots b_2$, $P_3 = a \dots b_3$ of length at least~1, two of which have length at least 2, vertex-disjoint except at $a$, and such that $b_1b_2b_3$ is a triangle and no edges exist between the paths except those of the triangle and the three edges incident to~$a$. An \emph{even hole} is a chordless cycle of even length. For three non-negative integers $i\leq j\leq k$, let $S_{i,j,k}$ be the tree with a vertex $v$, from which start three paths with $i$, $j$, and $k$ edges respectively. We denote by $K_t$ the complete graph on $t$ vertices. We prove that for all non-negative integers $i, j, k$, the class of graphs that contain no theta, no $K_3$, and no $S_{i, j, k}$ as induced subgraphs have bounded treewidth. We prove that for all non-negative integers $i, j, k, t$, the class of graphs that contain no even hole, no pyramid, no $K_t$, and no $S_{i, j, k}$ as induced subgraphs have bounded treewidth. To bound the treewidth, we prove that every graph of large treewidth must contain a large clique or a minimal separator of large cardinality.

Published
2021

9. (Theta, triangle)‐free and (even hole, K4)‐free graphs—Part 1: Layered wheels

Author

Nicolas Trotignon, Pegah Pournajafi, Modèles de calcul, Complexité, Combinatoire (MC2), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), ANR-10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon(2010), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-École normale supérieure - Lyon (ENS Lyon)

Subjects
Sequence, Plane (geometry), 010102 general mathematics, Induced subgraph, Boundary (topology), 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Intersection graph, 01 natural sciences, Combinatorics, Line segment, Intersection, 010201 computation theory & mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology, Rectangle, 0101 mathematics, ComputingMilieux_MISCELLANEOUS, Mathematics
Abstract

The Burling sequence is a sequence of triangle-free graphs of increasing chromatic number. Each of them is isomorphic to the intersection graph of a set of axis-parallel boxes in $R^3$. These graphs were also proved to have other geometrical representations: intersection graphs of line segments in the plane, and intersection graphs of frames, where a frame is the boundary of an axis-aligned rectangle in the plane. We call Burling graph every graph that is an induced subgraph of some graph in the Burling sequence. We give five new equivalent ways to define Burling graphs. Three of them are geometrical, one is of a more graph-theoretical flavour and one is more axiomatic.

Published
2021

10. The (theta, wheel)-free graphs Part IV: Induced paths and cycles

Author

Nicolas Trotignon, Kristina Vušković, Marko Radovanović, Modèles de calcul, Complexité, Combinatoire (MC2), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), ANR-10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon(2010), ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)

Subjects
010102 general mathematics, Induced subgraph, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, Theoretical Computer Science, Combinatorics, Computational Theory and Mathematics, 010201 computation theory & mathematics, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Combinatorics (math.CO), 0101 mathematics, Mathematics, Decomposition theorem
Abstract

International audience; A hole in a graph is a chordless cycle of length at least 4. A theta is a graph formed by three internally vertex-disjoint paths of length at least 2 between the same pair of distinct vertices. A wheel is a graph formed by a hole and a node that has at least 3 neighbors in the hole. In this series of papers we study the class of graphs that do not contain as an induced subgraph a theta nor a wheel. In Part II of the series we prove a decomposition theorem for this class, that uses clique cutsets and 2-joins. In this paper we use this decomposition theorem to solve several problems related to finding induced paths and cycles in our class.

Published
2021

11. On the complexity of colouring antiprismatic graphs

Author

Nicolas Trotignon, Cléophée Robin, Myriam Preissmann, Optimisation Combinatoire (G-SCOP_OC), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA), Modèles de calcul, Complexité, Combinatoire (MC2), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), ANR-10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon(2010), ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-École normale supérieure - Lyon (ENS Lyon)

Subjects
FOS: Computer and information sciences, Vertex (graph theory), Discrete Mathematics (cs.DM), General Computer Science, Applied Mathematics, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, Computer Science Applications, Combinatorics, Computer Science::Robotics, 010201 computation theory & mathematics, Theory of computation, FOS: Mathematics, 0202 electrical engineering, electronic engineering, information engineering, Mathematics - Combinatorics, 020201 artificial intelligence & image processing, Combinatorics (math.CO), Time complexity, Clique cover, Mathematics, Computer Science - Discrete Mathematics
Abstract

International audience; A graph G is prismatic if for every triangle T of G, every vertex of G not in T has a unique neighbour in T. The complement of a prismatic graph is called \emph{antiprismatic}. The complexity of colouring antiprismatic graphs is still unknown. Equivalently, the complexity of the clique cover problem in prismatic graphs is not known. Chudnovsky and Seymour gave a full structural description of prismatic graphs. They showed that the class can be divided into two subclasses: the orientable prismatic graphs, and the non-orientable prismatic graphs. We give a polynomial time algorithm that solves the clique cover problem in every non-orientable prismatic graph. It relies on the the structural description and on later work of Javadi and Hajebi. We give a polynomial time algorithm which solves the vertex-disjoint triangles problem for every prismatic graph. It does not rely on the structural description.

Published
2020

12. On the tree-width of even-hole-free graphs

Author

Pierre Aboulker, Nicolas Trotignon, Eun Jung Kim, Ni Luh Dewi Sintiari, Isolde Adler, Modèles de calcul, Complexité, Combinatoire (MC2), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), ANR-10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon(2010), Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-École normale supérieure - Lyon (ENS Lyon)

Subjects
FOS: Computer and information sciences, Property testing, Class (set theory), Discrete Mathematics (cs.DM), Induced subgraph, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, law.invention, Combinatorics, law, Line graph, Computer Science - Data Structures and Algorithms, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), [INFO]Computer Science [cs], 0101 mathematics, ComputingMilieux_MISCELLANEOUS, Mathematics, Conjecture, Degree (graph theory), 010102 general mathematics, 16. Peace & justice, Treewidth, 010201 computation theory & mathematics, Bounded function, Combinatorics (math.CO), Computer Science - Discrete Mathematics
Abstract

The class of all even-hole-free graphs has unbounded tree-width, as it contains all complete graphs. Recently, a class of (even-hole, K 4 )-free graphs was constructed, that still has unbounded tree-width (Sintiari and Trotignon, 2019). The class has unbounded degree and contains arbitrarily large clique-minors. We ask whether this is necessary. We prove that for every graph G , if G excludes a fixed graph H as a minor, then G either has small tree-width, or G contains a large wall or the line graph of a large wall as induced subgraph. This can be seen as a strengthening of Robertson and Seymour’s excluded grid theorem for the case of minor-free graphs. Our theorem implies that every class of even-hole-free graphs excluding a fixed graph as a minor has bounded tree-width. In fact, our theorem applies to a more general class: (theta, prism)-free graphs. This implies the known result that planar even hole-free graphs have bounded tree-width (Silva et al., 2010). We conjecture that even-hole-free graphs of bounded degree have bounded tree-width. If true, this would mean that even-hole-freeness is testable in the bounded-degree graph model of property testing. We prove the conjecture for subcubic graphs and we give a bound on the tree-width of the class of (even hole, pyramid)-free graphs of degree at most 4.

Published
2020

13. The (theta, wheel)-free graphs Part II: Structure theorem

Author

Nicolas Trotignon, Kristina Vušković, Marko Radovanović, Modèles de calcul, Complexité, Combinatoire (MC2), Laboratoire de l'Informatique du Parallélisme (LIP), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL)

Subjects
010102 general mathematics, Induced subgraph, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, Theoretical Computer Science, Vertex (geometry), Combinatorics, Computational Theory and Mathematics, 010201 computation theory & mathematics, FOS: Mathematics, Mathematics - Combinatorics, 05C75, Discrete Mathematics and Combinatorics, Combinatorics (math.CO), 0101 mathematics, Recognition algorithm, Mathematics, Decomposition theorem, Structured program theorem
Abstract

A hole in a graph is a chordless cycle of length at least 4. A theta is a graph formed by three paths between the same pair of distinct vertices so that the union of any two of the paths induces a hole. A wheel is a graph formed by a hole and a node that has at least 3 neighbors in the hole. In this paper we obtain a decomposition theorem for the class of graphs that do not contain an induced subgraph isomorphic to a theta or a wheel, i.e. the class of (theta, wheel)-free graphs. The decomposition theorem uses clique cutsets and 2-joins. Clique cutsets are vertex cutsets that work really well in decomposition based algorithms, but are unfortunately not general enough to decompose more complex hereditary graph classes. A 2-join is an edge cutset that appeared in decomposition theorems of several complex classes, such as perfect graphs, even-hole-free graphs and others. In these decomposition theorems 2-joins are used together with vertex cutsets that are more general than clique cutsets, such as star cutsets and their generalizations (which are much harder to use in algorithms). This is a first example of a decomposition theorem that uses just the combination of clique cutsets and 2-joins. This has several consequences. First, we can easily transform our decomposition theorem into a complete structure theorem for (theta, wheel)-free graphs, i.e. we show how every (theta, wheel)-free graph can be built starting from basic graphs that can be explicitly constructed, and gluing them together by prescribed composition operations; and all graphs built this way are (theta, wheel)-free. Such structure theorems are very rare for hereditary graph classes, only a few examples are known. Secondly, we obtain an O ( n 4 m ) -time decomposition based recognition algorithm for (theta, wheel)-free graphs. Finally, in Parts III and IV of this series, we give further applications of our decomposition theorem.

Published
2020

14. Graphs with polynomially many minimal separators

Author

Maria Chudnovsky, Nicolas Trotignon, Kristina Vušković, Stéphan Thomassé, Tara Abrishami, Cemil Dibek, Modèles de calcul, Complexité, Combinatoire (MC2), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), and ANR-10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon(2010)

Subjects
Class (set theory), 021103 operations research, 0211 other engineering and technologies, Induced subgraph, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Theoretical Computer Science, Combinatorics, Prism (geometry), Computational Theory and Mathematics, 010201 computation theory & mathematics, Independent set, Pyramid, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, [INFO]Computer Science [cs], Combinatorics (math.CO), Time complexity, Mathematics
Abstract

We show that graphs that do not contain a theta, pyramid, prism, or turtle as an induced subgraph have polynomially many minimal separators. This result is the best possible in the sense that there are graphs with exponentially many minimal separators if only three of the four induced subgraphs are excluded. As a consequence, there is a polynomial time algorithm to solve the maximum weight independent set problem for the class of (theta, pyramid, prism, turtle)-free graphs. Since every prism, theta, and turtle contains an even hole, this also implies a polynomial time algorithm to solve the maximum weight independent set problem for the class of (pyramid, even hole)-free graphs.

Published
2020
Full Text
View/download PDF

15. χ-bounds, operations, and chords

Author

Nicolas Trotignon, Lan Anh Pham, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS), Modèles de calcul, Complexité, Combinatoire (MC2), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), ANR-13-BS02-0007,Stint,Structures Interdites(2013), ANR-10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon(2010), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL)

Subjects
010102 general mathematics, Structure (category theory), 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Edge (geometry), 05C75, 05C15, 05C85, 01 natural sciences, Combinatorics, 010201 computation theory & mathematics, Computer Science - Data Structures and Algorithms, Mathematics - Combinatorics, Discrete Mathematics and Combinatorics, Graph (abstract data type), Chord (music), Geometry and Topology, 0101 mathematics, ComputingMilieux_MISCELLANEOUS, Computer Science - Discrete Mathematics, Mathematics
Abstract

A \emph{long unichord} in a graph is an edge that is the unique chord of some cycle of length at least 5. A graph is \emph{long-unichord-free} if it does not contain any long-unichord. We prove a structure theorem for long-unichord-free graph. We give an $O(n^4m)$-time algorithm to recognize them. We show that any long-unichord-free graph $G$ can be colored with at most $O(\omega^3)$ colors, where $\omega$ is the maximum number of pairwise adjacent vertices in $G$.

Published
2017

16. The Independent Set Problem Is FPT for Even-Hole-Free Graphs

Author

Edin Husić and Stéphan Thomassé and Nicolas Trotignon, Husić, Edin, Thomassé, Stéphan, Trotignon, Nicolas, Edin Husić and Stéphan Thomassé and Nicolas Trotignon, Husić, Edin, Thomassé, Stéphan, and Trotignon, Nicolas

Abstract

The class of even-hole-free graphs is very similar to the class of perfect graphs, and was indeed a cornerstone in the tools leading to the proof of the Strong Perfect Graph Theorem. However, the complexity of computing a maximum independent set (MIS) is a long-standing open question in even-hole-free graphs. From the hardness point of view, MIS is W[1]-hard in the class of graphs without induced 4-cycle (when parameterized by the solution size). Halfway of these, we show in this paper that MIS is FPT when parameterized by the solution size in the class of even-hole-free graphs. The main idea is to apply twice the well-known technique of augmenting graphs to extend some initial independent set.

Published
2019
Full Text
View/download PDF

17. Equistarable Graphs and Counterexamples to Three Conjectures on Equistable Graphs

Author

Nicolas Trotignon and Martin Milanič

Subjects
021103 operations research, Conjecture, 0211 other engineering and technologies, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Vertex (geometry), law.invention, Combinatorics, 010201 computation theory & mathematics, law, Converse, Line graph, Discrete Mathematics and Combinatorics, Partition (number theory), Maximal independent set, Geometry and Topology, Complement graph, Mathematics, Counterexample
Abstract

Equistable graphs are graphs admitting positive weights on vertices such that a subset of vertices is a maximal stable set if and only if it is of total weight 1. Strongly equistable graphs are graphs such that for every and every nonempty subset T of vertices that is not a maximal stable set, there exist positive vertex weights assigning weight 1 to every maximal stable set such that the total weight of T does not equal c. General partition graphs are the intersection graphs of set systems over a finite ground set U such that every maximal stable set of the graph corresponds to a partition of U. General partition graphs are exactly the graphs every edge of which is contained in a strong clique. In 1994, Mahadev, Peled, and Sun proved that every strongly equistable graph is equistable, and conjectured that the converse holds as well. In 2009, Orlin proved that every general partition graph is equistable, and conjectured that the converse holds as well. Orlin's conjecture, if true, would imply the conjecture due to Mahadev, Peled, and Sun. An “intermediate” conjecture, posed by Miklavic and Milanic in 2011, states that every equistable graph has a strong clique. The above conjectures have been verified for several graph classes. We introduce the notion of equistarable graphs and based on it construct counterexamples to all three conjectures within the class of complements of line graphs of triangle-free graphs. We also show that not all strongly equistable graphs are general partition.

Published
2016

18. On Triangle-Free Graphs That Do Not Contain a Subdivision of the Complete Graph on Four Vertices as an Induced Subgraph

Author

Nicolas Trotignon and Kristina Vušković

Subjects
Mathematics::Combinatorics, business.industry, 010102 general mathematics, Complete graph, Induced subgraph, 0102 computer and information sciences, 01 natural sciences, Graph, Combinatorics, Computer Science::Discrete Mathematics, 010201 computation theory & mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology, 0101 mathematics, business, Mathematics, Subdivision, Decomposition theorem
Abstract

We prove a decomposition theorem for the class of triangle-free graphs that do not contain a subdivision of the complete graph on four vertices as an induced subgraph. We prove that every graph of girth at least~5 in this class is 3-colorable.

Published
2016

20. Using SPQR-trees to speed up algorithms based on 2-cutset decompositions

Author

Nicolas Trotignon, H.B. de Macedo Filho, Z. Li, Raphael C. S. Machado, C.M.H. de Figueiredo, Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia (COPPE-UFRJ), Universidade Federal do Rio de Janeiro (UFRJ), Laboratoire d'informatique de l'école normale supérieure (LIENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), National Institute of Metrology, Quality and Technology [Rio de Janeiro] (Inmetro ), Modèles de calcul, Complexité, Combinatoire (MC2), Laboratoire de l'Informatique du Parallélisme (LIP), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), and Thomassé, Stéphan

Subjects
Block graph, SPQR tree, Applied Mathematics, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Voltage graph, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO] Computer Science [cs], Tree decomposition, law.invention, Pathwidth, law, Line graph, Discrete Mathematics and Combinatorics, Graph (abstract data type), [INFO]Computer Science [cs], Algorithm, ComputingMilieux_MISCELLANEOUS, Implicit graph, MathematicsofComputing_DISCRETEMATHEMATICS, Mathematics
Abstract

We propose the use of SPQR-trees as a data structure to encode the 3-connected components of a graph and to obtain linear-time recognition algorithms for graph classes structurally characterized by 2-cutset decompositions.

Published
2015

21. Preface: Algorithmic Graph Theory on the Adriatic Coast

Author

Daniël Paulusma, Primoz Potocnik, Nicolas Trotignon, Martin Milanič, Pinar Heggernes, Boštjan Brešar, and Marcin Kamiński

Subjects
Theoretical computer science, Operations research, Applied Mathematics, Discrete Mathematics and Combinatorics, Algorithmic graph theory, Mathematics
Published
2017

22. Stable Sets in {ISK4,wheel}-Free Graphs

Author

Irena Penev, Nicolas Trotignon, Martin Milanič, University of Primorska, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Modèles de calcul, Complexité, Combinatoire (MC2), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Centre National de la Recherche Scientifique (CNRS), ANR-13-BS02-0007,Stint,Structures Interdites(2013), ANR-10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon(2010), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)

Subjects
General Computer Science, Induced subgraph, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Combinatorics, Computer Science::Discrete Mathematics, FOS: Mathematics, Mathematics - Combinatorics, 0101 mathematics, ComputingMilieux_MISCELLANEOUS, Subdivision, Mathematics, business.industry, Applied Mathematics, 010102 general mathematics, Complete graph, Graph, Vertex (geometry), Computer Science Applications, 010201 computation theory & mathematics, Independent set, Theory of computation, Combinatorics (math.CO), business, Computer Science(all)
Abstract

An ISK4 in a graph G is an induced subgraph of G that is isomorphic to a subdivision of \(K_4\) (the complete graph on four vertices). A wheel is a graph that consists of a chordless cycle, together with a vertex that has at least three neighbors in the cycle. A graph is {ISK4,wheel}-free if it has no ISK4 and does not contain a wheel as an induced subgraph. We give an \(O(|V(G)|^7)\)-time algorithm to compute the maximum weight of a stable set in an input weighted {ISK4,wheel}-free graph G with non-negative integer weights.

Published
2018

23. Wheel-free planar graphs

Author

Pierre Aboulker, Maria Chudnovsky, Paul Seymour, Nicolas Trotignon, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science [New York], Columbia University [New York], Princeton University, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Modèles de calcul, Complexité, Combinatoire (MC2), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), ANR-13-BS02-0007,Stint,Structures Interdites(2013), ANR-10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon(2010), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL)

Subjects
Block graph, Factor-critical graph, Discrete mathematics, 010102 general mathematics, Induced subgraph, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Butterfly graph, Computer Science::Robotics, Combinatorics, Computer Science::Discrete Mathematics, 010201 computation theory & mathematics, FOS: Mathematics, Wheel graph, Mathematics - Combinatorics, 05C75, Discrete Mathematics and Combinatorics, Combinatorics (math.CO), 0101 mathematics, Computer Science::Data Structures and Algorithms, Mathematics, Universal graph, Distance-hereditary graph, Forbidden graph characterization
Abstract

International audience; A \emph{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.

Published
2015

24. Triangle-free graphs that do not contain an induced subdivision of $K_4$ are 3-colorable

Author

Chun-Hung Liu, Maria Chudnovsky, Oliver Schaudt, Nicolas Trotignon, Sophie Spirkl, and Kristina Vušković

Subjects
Conjecture, business.industry, 010102 general mathematics, Induced subgraph, Graph theory, 0102 computer and information sciences, Computer Science::Computational Geometry, 01 natural sciences, Combinatorics, 010201 computation theory & mathematics, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Combinatorics (math.CO), Geometry and Topology, 0101 mathematics, business, Mathematics, Subdivision
Abstract

We show that triangle-free graphs that do not contain an induced subgraph isomorphic to a subdivision of K4 are 3-colorable. This proves a conjecture of Trotignon and Vuskovic [J. Graph Theory. 84 (2017), no. 3, pp. 233–248].

Published
2017

25. A Polynomial Turing-Kernel for Weighted Independent Set in Bull-Free Graphs

Author

Stéphan Thomassé, Nicolas Trotignon, Kristina Vušković, Modèles de calcul, Complexité, Combinatoire (MC2), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Institut Universitaire de France (IUF), Ministère de l'Education nationale, de l’Enseignement supérieur et de la Recherche (M.E.N.E.S.R.), School of Computing [Leeds], University of Leeds, ANR-13-BS02-0007,Stint,Structures Interdites(2013), ANR-10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon(2010), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), and Thomassé, Stéphan

Subjects
Polynomial, General Computer Science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, Chromatic polynomial, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Matrix polynomial, Square-free polynomial, Combinatorics, Polynomial kernel, Chordal graph, Computer Science::Discrete Mathematics, Degree of a polynomial, Chromatic scale, 0101 mathematics, Time complexity, ComputingMilieux_MISCELLANEOUS, Mathematics, Alternating polynomial, Applied Mathematics, 010102 general mathematics, Function (mathematics), Graph, Computer Science Applications, 010201 computation theory & mathematics, Bounded function, Independent set, Maximal independent set, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract

The maximum stable set problem is NP-hard, even when restricted to triangle-free graphs. In particular, one cannot expect a polynomial time algorithm deciding if a bull-free graph has a stable set of size k, when k is part of the instance. Our main result in this paper is to show the existence of an FPT algorithm when we parameterize the problem by the solution size k. A polynomial kernel is unlikely to exist for this problem. We show however that our problem has a polynomial size Turing-kernel. More precisely, the hard cases are instances of size O(k 5 ). As a byproduct, if we forbid odd holes in addition to the bull, we show the existence of a polynomial time algorithm for the stable set problem. We also prove that the chromatic number of a bull-free graph is bounded by a function of its clique number and the maximum chromatic number of its triangle-free induced subgraphs. All our results rely on a decomposition theorem of bull-free graphs due to Chudnovsky which is modified here, allowing us to provide extreme decompositions, adapted to our computational purpose.

Published
2017

26. Linear Balanceable and Subcubic Balanceable Graphs*

Author

Théophile Trunck, Nicolas Trotignon, Marko Radovanović, Pierre Aboulker, and Kristina Vušković

Subjects
Combinatorics, 021103 operations research, Conjecture, 010201 computation theory & mathematics, 0211 other engineering and technologies, Bipartite graph, Discrete Mathematics and Combinatorics, Chord (music), 0102 computer and information sciences, 02 engineering and technology, Geometry and Topology, 01 natural sciences, Mathematics
Abstract

In Math Program 55(1992), 129–168, Conforti and Rao conjectured that every balanced bipartite graph contains an edge that is not the unique chord of a cycle. We prove this conjecture for balanced bipartite graphs that do not contain a cycle of length 4 (also known as linear balanced bipartite graphs), and for balanced bipartite graphs whose maximum degree is at most 3. We in fact obtain results for more general classes, namely linear balanceable and subcubic balanceable graphs. Additionally, we prove that cubic balanced graphs contain a pair of twins, a result that was conjectured by Morris, Spiga, and Webb in ( Discrete Math 310(2010), 3228–3235).

Published
2013

27. Isolating Highly Connected Induced Subgraphs

Author

Nicolas Trotignon, Stéphan Thomassé, Irena Penev, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Modèles de calcul, Complexité, Combinatoire (MC2), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Institut Universitaire de France (IUF), Ministère de l'Education nationale, de l’Enseignement supérieur et de la Recherche (M.E.N.E.S.R.), ANR-13-BS02-0007,Stint,Structures Interdites(2013), ANR-10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon(2010), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), and Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL)

Subjects
extreme decomposition theorem, General Mathematics, Existential quantification, Vertex connectivity, Induced subgraph, Hereditary class, Decomposition theorems, 0102 computer and information sciences, 01 natural sciences, Domain decomposition methods, Combinatorics, Computer Science::Discrete Mathematics, chromatic number, FOS: Mathematics, Mathematics (all), Mathematics - Combinatorics, [INFO]Computer Science [cs], Chromatic scale, 0101 mathematics, [MATH]Mathematics [math], 10. No inequality, Mathematics, Discrete mathematics, Connectivity, Mathematics::Combinatorics, hereditary classes of graphs, 010102 general mathematics, Chromatic number, Graph theory, graph, Graph, operations on graphs, 010201 computation theory & mathematics, connectivity, 05C75, Combinatorics (math.CO), Graph operations
Abstract

International audience; We prove that any graph $G$ of minimum degree greater than $2k^2-1$ has a $(k+1)$-connected induced subgraph $H$ such that the number of vertices of $H$ that have neighbors outside of $H$ is at most $2k^2-1$. This generalizes a classical result of Mader, which states that a high minimum degree implies the existence of a highly connected subgraph. We give several variants of our result, and for each of these variants, we give asymptotics for the bounds. We also compute optimal values for the case when $k=2$. Alon, Kleitman, Saks, Seymour, and Thomassen proved that in a graph of high chromatic number, there exists an induced subgraph of high connectivity and high chromatic number. We give a new proof of this theorem with a better bound.

Published
2016

28. Perfect graphs of arbitrarily large clique-chromatic number

Author

Pierre Charbit, Irena Penev, Stéphan Thomassé, Nicolas Trotignon, Networks, Graphs and Algorithms (GANG), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Modèles de calcul, Complexité, Combinatoire (MC2), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Institut Universitaire de France (IUF), Ministère de l'Education nationale, de l’Enseignement supérieur et de la Recherche (M.E.N.E.S.R.), ANR-13-BS02-0007,Stint,Structures Interdites(2013), ANR-10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon(2010), Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and ANR-11-IDEX-0007-02/10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon(2011)

Subjects
clique, 05C15, 05C17, 010102 general mathematics, 0102 computer and information sciences, Clique (graph theory), 01 natural sciences, Theoretical Computer Science, Combinatorics, Arbitrarily large, Computational Theory and Mathematics, 010201 computation theory & mathematics, Perfect graph, FOS: Mathematics, Mathematics - Combinatorics, Discrete Mathematics and Combinatorics, [INFO]Computer Science [cs], Chromatic scale, Combinatorics (math.CO), 0101 mathematics, [MATH]Mathematics [math], coloring, Mathematics
Abstract

We prove that there exist perfect graphs of arbitrarily large clique-chromatic number. These graphs can be obtained from cobipartite graphs by repeatedly gluing along cliques. This negatively answers a question raised by Duffus, Sands, Sauer, and Woodrow in [Two-coloring all two-element maximal antichains, J. Combinatorial Theory, Ser. A, 57 (1991), 109-116].

Published
2016

29. Finding an induced subdivision of a digraph

Author

Frédéric Havet, Nicolas Trotignon, Jørgen Bang-Jensen, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Department of Mathematics and Computer Science [Odense] (IMADA), University of Southern Denmark (SDU), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Financial support from the Danish National Science research council (FNU) (under grant no. 09-066741)., Electronic Notes on Discrete Mathematics, ANR-09-BLAN-0159,AGAPE,Algorithmes de graphes parametres et exacts(2009), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and INRIA

Subjects
FOS: Computer and information sciences, Polynomial, Discrete Mathematics (cs.DM), General Computer Science, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Mathematical proof, 01 natural sciences, Theoretical Computer Science, Combinatorics, 3-SAT, Computer Science::Discrete Mathematics, FOS: Mathematics, 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, 05C85, Mathematics, Subdivision, Discrete mathematics, Mathematics::Combinatorics, business.industry, Applied Mathematics, 020206 networking & telecommunications, Digraph, Graph, NP-completeness, induced paths and cycles, 010201 computation theory & mathematics, Combinatorics (math.CO), linkings, business, Computer Science(all), Computer Science - Discrete Mathematics, digraphs
Abstract

International audience; We consider the following problem for oriented graphs and digraphs: Given an oriented graph (digraph) G, does it contain an induced subdivision of a prescribed digraph D? The complexity of this problem depends on D and on whether G must be an oriented graph or is allowed to contain 2-cycles. We give a number of examples of polynomial instances as well as several NP-completeness proofs.

Published
2012

30. Excluding Induced Subdivisions of the Bull and Related Graphs

Author

Nicolas Trotignon, Alex Scott, Irena Penev, and Maria Chudnovsky

Subjects
Vertex (graph theory), Mathematics::Combinatorics, Conjecture, Matching (graph theory), 010102 general mathematics, Necklace, Graph theory, 0102 computer and information sciences, Function (mathematics), 01 natural sciences, Omega, Combinatorics, 010201 computation theory & mathematics, Path (graph theory), Discrete Mathematics and Combinatorics, Geometry and Topology, 0101 mathematics, Mathematics
Abstract

For any graph $H$, let ${\rm Forb}^*(H)$ be the class of graphs with no induced subdivision of $H$. It was conjectured in [A.D. Scott, Induced trees in graphs of large chromatic number, {\em Journal of Graph Theory}, 24:297--311, 1997] that, for every graph $H$, there is a function $f_H:\mathbb{N} \rightarrow \mathbb{R}$ such that for every graph $G \in {\rm Forb}^*(H)$, $\chi(G) \leq f_H(\omega(G))$. We prove this conjecture for several graphs $H$, namely the paw (a triangle with a pendant edge), the bull (a triangle with two vertex-disjoint pendant edges), and what we call a "necklace," that is, a graph obtained from a path by choosing a matching such that no edge of the matching is incident with an endpoint of the path, and for each edge of the matching, adding a vertex adjacent to the ends of this edge.

Published
2011

31. The k-in-a-tree problem for graphs of girth at least k

Author

Nicolas Trotignon and W. Liu

Subjects
Discrete mathematics, Applied Mathematics, 010102 general mathematics, Induced subgraph, 0102 computer and information sciences, 01 natural sciences, Tree (graph theory), Graph, Combinatorics, Integer, 010201 computation theory & mathematics, Discrete Mathematics and Combinatorics, 0101 mathematics, Mathematics
Abstract

For all integers k>=3, we give an O(n^4)-time algorithm for the problem whose instance is a graph G of girth at least k together with k vertices and whose question is ''Does G contains an induced subgraph containing the k vertices and isomorphic to a tree?''. This directly follows for k=3 from the three-in-a-tree algorithm of Chudnovsky and Seymour and for k=4 from a result of Derhy, Picouleau and Trotignon. Here we solve the problem for k>=5. Our algorithm relies on a structural description of graphs of girth at least k that do not contain an induced tree covering k given vertices (k>=5).

Published
2010

32. The Four-in-a-Tree Problem in Triangle-Free Graphs

Author

Christophe Picouleau, Nicolas Trotignon, and Nicolas Derhy

Subjects
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Existential quantification, Graph, four,tree,algorithm,triangle-free graph,Three,trois,quatre,arbre,algorithme,3-in-a-tree,4-in-a-tree,graphes sans triangles, Theoretical Computer Science, Vertex (geometry), Combinatorics, FOS: Mathematics, Mathematics - Combinatorics, Discrete Mathematics and Combinatorics, Partition (number theory), 05C85, Combinatorics (math.CO), Computer Science - Discrete Mathematics, Mathematics
Abstract

The three-in-a-tree algorithm of Chudnovsky and Seymour decides in time O(n4) whether three given vertices of a graph belong to an induced tree. Here, we study four-in-a-tree for triangle-free graphs. We give a structural answer to the following question : how does look like a triangle-free graph such that no induced tree covers four given vertices ? Our main result says that any such graph must have the "same structure", in a sense to be defined precisely, as a square or a cube. We provide an O(nm)-time algorithm that given a triangle-free graph G together with four vertices outputs either an induced tree that contains them or a partition of V(G) certifying that no such tree exists. We prove that the problem of deciding whether there exists a tree T covering the four vertices such that at most one vertex of T has degree at least 3 is NP-complete., L'algorithme "three-in-a-tree" de Chudnovsky et Seymour décide en temps O(n4) si trois sommets donnés d'un graphe appartiennent à un arbre induit. Ici, nous étudions four-in-a-tree pour les graphes sans triangles. Nous donnons une réponse structurelle à la question suivante : à quoi ressemble un graphe sans triangles dont aucun arbre induit ne couvre quatre sommets donnés ? Notre résultat principal affirme qu'un tel graphe doit avoir la "même structure", dans un sens précisemment défini, qu'un carré ou un cube. Nous donnons un algorithme en temps O(nm) qui étant donné un graphe sans triangles G et quatre de ses sommets, retourne ou bien un arbre induit qui contient les sommets, ou bien une partition de V(G) certifiant qu'un tel arbre n'existe pas. Nous prouvons que le problème consistant à décider s'il existe un arbre T couvrant les quatre sommets et tel qu'au plus un sommet de T est de degré au moins 3 est NP-complet.

Published
2009

33. Decomposing Berge graphs and detecting balanced skew partitions

Author

Nicolas Trotignon, Centre d'économie de la Sorbonne (CES), Université Paris 1 Panthéon-Sorbonne (UP1)-Centre National de la Recherche Scientifique (CNRS), This work has been partially supported by ADONET network, a Marie Curie training network of the European Community., and European Mathematical Society

Subjects
2-Join, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Berge graphs, 01 natural sciences, Constructive, Theoretical Computer Science, Balanced skew partition, Combinatorics, Skew partition, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Mathematics - Combinatorics, Discrete Mathematics and Combinatorics, Berge graph, 0101 mathematics, skew partition, Mathematics, Decomposition theorem, Decomposition, Decomposing, 010102 general mathematics, balanced, Skew, Graph, 05C17, Detection, Recognition, recognition,Perfect graph,Berge graph,2-join,balanced skew partition,decomposition,detection,recognition.,Graphe parfait,graphe de Berge,reconnaissance, Computational Theory and Mathematics, 010201 computation theory & mathematics, Perfect graph, Combinatorics (math.CO), Basic class
Abstract

We prove that the problem of deciding whether a graph has a balanced skew partition is NP-hard. We give an O(n9)-time algorithm for the same problem restricted to Berge graphs. Our algorithm is not constructive : it certifies that a graph has a balanced skew partition if it has one. It relies on a new decomposition theorem for Berge graphs, that is more precise than the previously known theorems and implies them easily. Our theorem also implies that every Berge graph can be decomposed in a first step by using only balanced skew partitions, and in a second step by using only 2-joins. Our proof of this new theorem uses at an essential step one of the decomposition theorems of Chudnovsky., Nous prouvons que le problème de décider si un graphe possède une partition antisymétrique paire (balanced skew partition) est NP-difficile. Nous donnons un algorithme de complexité O(n9) pour le même problème restreint aux graphes de Berge. Notre algorithme n'est pas constructif : il certifie qu'un graphe possède une balanced skew partition quand il en possède une. Il repose un nouveau théorème de décomposition des graphes de Berge plus précis que les théorèmes précédemment connus. Notre théorème implique que tout graphe de Berge peut être décomposé dans un premier temps par des balanced skew partitions, puis dans un deuxième temps par des 2-joins. Notre preuve de ce nouveau théorème repose sur un théorème de décomposition dû à Chudnovsky.

Published
2008

35. Vertex elimination orderings for hereditary graph classes

Author

Pierre Charbit, Nicolas Trotignon, Kristina Vušković, Pierre Aboulker, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Networks, Graphs and Algorithms (GANG), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Modèles de calcul, Complexité, Combinatoire (MC2), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), School of Computing [Leeds], University of Leeds, ANR-13-BS02-0007,Stint,Structures Interdites(2013), ANR-10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon(2010), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)

Subjects
Discrete mathematics, Vertex (graph theory), FOS: Computer and information sciences, General method, Discrete Mathematics (cs.DM), 010102 general mathematics, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 16. Peace & justice, 01 natural sciences, Graph, Theoretical Computer Science, Combinatorics, 010201 computation theory & mathematics, Chordal graph, FOS: Mathematics, Mathematics - Combinatorics, Discrete Mathematics and Combinatorics, 05C75, Combinatorics (math.CO), 0101 mathematics, Computer Science - Discrete Mathematics, Mathematics, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract

International audience; We provide a general method to prove the existence and compute efficiently elimination orderings in graphs. Our method relies on several tools that were known before, but that were not put together so far: the algorithm LexBFS due to Rose, Tarjan and Lueker, one of its properties discovered by Berry and Bordat, and a local decomposition property of graphs discovered by Maffray, Trotignon and Vu\vskovi\'c. We use this method to prove the existence of elimination orderings in several classes of graphs, and to compute them in linear time. Some of the classes have already been studied, namely even-hole-free graphs, square-theta-free Berge graphs, universally signable graphs and wheel-free graphs. Some other classes are new. It turns out that all the classes that we study in this paper can be defined by excluding some of the so-called Truemper configurations. For several classes of graphs, we obtain directly bounds on the chromatic number, or fast algorithms for the maximum clique problem or the coloring problem.

Published
2015

36. Algorithms for Perfectly Contractile Graphs

Author

Frédéric Maffray, Nicolas Trotignon, Optimisation Combinatoire (G-SCOP_OC), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Leibniz (Leibniz - IMAG), Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Grenoble (INPG)-Université Joseph Fourier - Grenoble 1 (UJF), Université Joseph Fourier - Grenoble 1 (UJF)-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), CEntre de Recherche en Mathématiques, Statistique et Économie Mathématique (CERMSEM), Université Paris 1 Panthéon-Sorbonne (UP1)-Centre National de la Recherche Scientifique (CNRS), and Maffray, Frédéric

Subjects
General Mathematics, Physics::Optics, 0102 computer and information sciences, Disjoint sets, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Combinatorics, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Perfect graph, Mathematics - Combinatorics, 05C85, 0101 mathematics, perfectly contractile graph, Recognition algorithm, Time complexity, coloring, ComputingMilieux_MISCELLANEOUS, Mathematics, Discrete mathematics, 010102 general mathematics, AMS 05C17 05C85 68R10, Graph, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], 010201 computation theory & mathematics, perfect graph, recognition, Computer Science - Discrete Mathematics
Abstract

We consider the class ${\cal A}$ of graphs that contain no odd hole, no antihole of length at least 5, and no "prism" (a graph consisting of two disjoint triangles with three disjoint paths between them) and the class ${\cal A}'$ of graphs that contain no odd hole, no antihole of length at least 5 and no odd prism (prism whose three paths are odd). These two classes were introduced by Everett and Reed and are relevant to the study of perfect graphs. We give polynomial-time recognition algorithms for these two classes. We proved previously that every graph $G\in{\cal A}$ is "perfectly contractile", as conjectured by Everett and Reed [see the chapter "Even pairs" in the book {\it Perfect Graphs}, J.L. Ram\'{\i}rez-Alfons\'{\i}n and B.A. Reed, eds., Wiley Interscience, 2001]. The analogous conjecture concerning graphs in ${\cal A}'$ is still open.

Published
2005

37. Ramsey-type results on singletons, co-singletons and monotone sequences in large collections of sets

Author

Nicolas Trotignon, Jérôme Renault, Sylvain Gravier, and Frédéric Maffray

Subjects
Discrete mathematics, Existential quantification, Value (computer science), Incidence matrix, Type (model theory), Theoretical Computer Science, Combinatorics, Set (abstract data type), Matrix (mathematics), Monotone polygon, Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Geometry and Topology, Mathematics
Abstract

We say that a 0-1 matrix $N$ of size $a\times b$ can be found in a collection of sets $\mathcal{H}$ if we can find sets $H_{1}, H_{2}, \dots, H_{a}$ in $\mathcal{H}$ and elements $e_1, e_2, \dots, e_b$ in $\cup_{H \in \mathcal{H}} H$ such that $N$ is the incidence matrix of the sets $H_{1}, H_{2}, \dots, H_{a}$ over the elements $e_1, e_2, \dots, e_b$. We prove the following Ramsey-type result: for every $n\in \N$, there exists a number S(n) such that in any collection of at least S(n) sets, one can find either the incidence matrix of a collection of $n$ singletons, or its complementary matrix, or the incidence matrix of a collection of $n$ sets completely ordered by inclusion. We give several results of the same extremal set theoretical flavour. For some of these, we give the exact value of the number of sets required.

Published
2004
Full Text
View/download PDF

38. A class of perfectly contractile graphs

Author

Nicolas Trotignon, Frédéric Maffray, Laboratoire Leibniz (Leibniz - IMAG), Université Joseph Fourier - Grenoble 1 (UJF)-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), Centre d'économie de la Sorbonne (CES), and Université Paris 1 Panthéon-Sorbonne (UP1)-Centre National de la Recherche Scientifique (CNRS)

Subjects
coloring algorithm, 010102 general mathematics, Even pair, 0102 computer and information sciences, Disjoint sets, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, AMS 05C17 05C15 05C85 68R10, Theoretical Computer Science, Combinatorics, Algorithm, 05C17, Computational Theory and Mathematics, 010201 computation theory & mathematics, Coloring algorithm, Perfect graph, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Coloring, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, 0101 mathematics, Mathematics, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract

We consider the class ${\cal A}$ of graphs that contain no odd hole, no antihole, and no "prism" (a graph consisting of two disjoint triangles with three disjoint paths between them). We prove that every graph $G\in{\cal A}$ different from a clique has an "even pair" (two vertices that are not joined by a chordless path of odd length), as conjectured by Everett and Reed [see the chapter "Even pairs" in the book {\it Perfect Graphs}, J.L. Ram\'{\i}rez-Alfons\'{\i}n and B.A. Reed, eds., Wiley Interscience, 2001]. Our proof is a polynomial-time algorithm that produces an even pair with the additional property that the contraction of this pair yields a graph in ${\cal A}$. This entails a polynomial-time algorithm, based on successively contracting even pairs, to color optimally every graph in ${\cal A}$. This generalizes several results concerning some classical families of perfect graphs.

Published
2013

39. Detecting wheels

Author

Nicolas Trotignon, Emilie Diot, Sébastien Tavenas, Service de Médecine Interne, Hôpital Bretonneau, Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Modèles de calcul, Complexité, Combinatoire (MC2), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), ANR-13-BS02-0007,Stint,Structures Interdites(2013), ANR-11-IDEX-0007-02/10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon(2011), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), ANR-10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon(2010), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), and Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL)

Subjects
FOS: Computer and information sciences, Vertex (graph theory), Discrete Mathematics (cs.DM), Applied Mathematics, 010102 general mathematics, Induced subgraph, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Combinatorics, 010201 computation theory & mathematics, FOS: Mathematics, Discrete Mathematics and Combinatorics, Graph (abstract data type), Mathematics - Combinatorics, 05C75, Combinatorics (math.CO), 0101 mathematics, Analysis, Mathematics, Computer Science - Discrete Mathematics
Abstract

A wheel is a graph made of a cycle of length at least 4 together with a vertex that has at least three neighbors in the cycle. We prove that the problem whose instance is a graph G and whose question is "does G contains a wheel as an induced subgraph" is NP-complete. We also settle the complexity of several similar problems. [LABEX MILYON (ANR-10-LABX-0070) of Universit? de Lyon]

Published
2013

40. Substitution and $\chi$-Boundedness

Author

Nicolas Trotignon, Maria Chudnovsky, Irena Penev, and Alex Scott

Subjects
Polynomial (hyperelastic model), 010102 general mathematics, Substitution (algebra), 0102 computer and information sciences, Function (mathematics), Clique (graph theory), 01 natural sciences, Omega, Theoretical Computer Science, Exponential function, Combinatorics, Computational Theory and Mathematics, Closure (mathematics), 010201 computation theory & mathematics, Bounded function, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, 0101 mathematics, Mathematics
Abstract

A class $\mathcal{G}$ of graphs is said to be {\em $\chi$-bounded} if there is a function $f:\mathbb{N} \rightarrow \mathbb{R}$ such that for all $G \in \mathcal{G}$ and all induced subgraphs $H$ of $G$, $\chi(H) \leq f(\omega(H))$. In this paper, we show that if $\mathcal{G}$ is a $\chi$-bounded class, then so is the closure of $\mathcal{G}$ under any one of the following three operations: substitution, gluing along a clique, and gluing along a bounded number of vertices. Furthermore, if $\mathcal{G}$ is $\chi$-bounded by a polynomial (respectively: exponential) function, then the closure of $\mathcal{G}$ under substitution is also $\chi$-bounded by some polynomial (respectively: exponential) function. In addition, we show that if $\mathcal{G}$ is a $\chi$-bounded class, then the closure of $\mathcal{G}$ under the operations of gluing along a clique and gluing along a bounded number of vertices together is also $\chi$-bounded, as is the closure of $\mathcal{G}$ under the operations of substitution and gluing along a clique together.

Published
2013

41. Complements of not so perfect graphs

Author

András Sebő, Zhentao Li, Raphael Machado, Stéphan Thomassé, Nicolas Trotignon, Optimisation Combinatoire (G-SCOP_OC), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), Department of Mathematics and Statistics [Montréal], McGill University = Université McGill [Montréal, Canada], Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Leibniz (Leibniz - IMAG), Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Grenoble (INPG)-Université Joseph Fourier - Grenoble 1 (UJF), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université Joseph Fourier - Grenoble 1 (UJF)-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), and Perruet, Marie Josèphe

Subjects
[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2013

42. Complexity of colouring problems restricted to unichord-free and \{square,unichord\}-free graphs

Author

Nicolas Trotignon, Celina M. H. de Figueiredo, Raphael C. S. Machado, Evendro Chagas Institut, Programa de Engenharia de Sistemas e Computação (PESC/COPPE-UFRJ), Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia (COPPE-UFRJ), Universidade Federal do Rio de Janeiro (UFRJ)-Universidade Federal do Rio de Janeiro (UFRJ), Laboratoire de l'Informatique du Parallélisme (LIP), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), Modèles de calcul, Complexité, Combinatoire (MC2), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), ANR-13-BS02-0007,Stint,Structures Interdites(2013), ANR-10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon(2010), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL)

Subjects
Discrete mathematics, FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Applied Mathematics, Complete graph, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Graph, Combinatorics, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, 05C85, Graph algorithms, Combinatorics (math.CO), Complement graph, Structured program theorem, Mathematics, Computer Science - Discrete Mathematics
Abstract

International audience; A \emph{unichord} in a graph is an edge that is the unique chord of a cycle. A \emph{square} is an induced cycle on four vertices. A graph is \emph{unichord-free} if none of its edges is a unichord. We give a slight restatement of a known structure theorem for unichord-free graphs and use it to show that, with the only exception of the complete graph $K_4$, every square-free, unichord-free graph of maximum degree~3 can be total-coloured with four colours. Our proof can be turned into a polynomial time algorithm that actually outputs the colouring. This settles the class of square-free, unichord-free graphs as a class for which edge-colouring is NP-complete but total-colouring is polynomial.

Published
2013
Full Text
View/download PDF

43. Edge-colouring and total-colouring chordless graphs

Author

Raphael C. S. Machado, Nicolas Trotignon, and Celina M. H. de Figueiredo

Subjects
Discrete mathematics, FOS: Computer and information sciences, Mathematics::Combinatorics, Foster graph, Discrete Mathematics (cs.DM), Butterfly graph, Theoretical Computer Science, Combinatorics, Edge coloring, Coxeter graph, Windmill graph, Computer Science::Discrete Mathematics, Friendship graph, FOS: Mathematics, Mathematics - Combinatorics, Discrete Mathematics and Combinatorics, 05C75, Chromatic scale, Combinatorics (math.CO), Time complexity, Computer Science - Discrete Mathematics, Mathematics
Abstract

A graph G is chordless if no cycle in G has a chord. In the present work we investigate the chromatic index and total chromatic number of chordless graphs. We describe a known decomposition result for chordless graphs and use it to establish that every chordless graph of maximum degree Δ ≥ 3 has chromatic index Δ and total chromatic number Δ + 1 . The proofs are algorithmic in the sense that we actually output an optimal colouring of a graph instance in polynomial time.

Published
2013
Full Text
View/download PDF

44. On Roussel-Rubio-type lemmas and their consequences

Author

Kristina Vušković and Nicolas Trotignon

Subjects
Mathematics::Classical Analysis and ODEs, 0102 computer and information sciences, Mathematical proof, 01 natural sciences, Theoretical Computer Science, Combinatorics, Chordal graph, Perfect graph, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Berge graph, 0101 mathematics, Mathematics, Decomposition theorem, Discrete mathematics, Lemma (mathematics), Even pair, 010102 general mathematics, Strong perfect graph theorem, Roussel–Rubio Lemma, 05C17, Weakly chordal graph, 010201 computation theory & mathematics, Pumping lemma for context-free languages, Combinatorics (math.CO)
Abstract

Roussel and Rubio proved a lemma which is essential in the proof of the Strong Perfect Graph Theorem. We give a new short proof of the main case of this lemma. In this note, we also give a short proof of Hayward’s decomposition theorem for weakly chordal graphs, relying on a Roussel–Rubio-type lemma. We recall how Roussel–Rubio-type lemmas yield very short proofs of the existence of even pairs in weakly chordal graphs and Meyniel graphs.

Published
2013
Full Text
View/download PDF

45. Coloring perfect graphs with no balanced skew-partitions

Author

Théophile Trunck, Maria Chudnovsky, Nicolas Trotignon, Kristina Vušković, Department of Computer Science [New York], Columbia University [New York], Modèles de calcul, Complexité, Combinatoire (MC2), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Faculty of Mathematics, Informatics, and Mechanics [Warsaw] (MIMUW), University of Warsaw (UW), School of Computing [Leeds], University of Leeds, ANR-13-BS02-0007,Stint,Structures Interdites(2013), ANR-10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon(2010), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)

Subjects
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Perfect graphs, Homogeneous pair, 010102 general mathematics, Skew, Maximum stable set, 0102 computer and information sciences, 01 natural sciences, Berge graphs, Theoretical Computer Science, Combinatorics, 05C17, Computational Theory and Mathematics, 010201 computation theory & mathematics, Independent set, Perfect graph, Skew partition, Discrete Mathematics and Combinatorics, Coloring, [INFO]Computer Science [cs], 0101 mathematics, 2-join, Computer Science - Discrete Mathematics, Mathematics
Abstract

International audience; We present an $O(n^5)$ algorithm that computes a maximum stable set of any perfect graph with no balanced skew-partition. We present $O(n^7)$ time algorithm that colors them.

Published
2013
Full Text
View/download PDF

46. Detecting an induced net subdivision

Author

Paul Seymour, Nicolas Trotignon, and Maria Chudnovsky

Subjects
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), business.industry, Subroutine, 010102 general mathematics, Induced subgraph, 0102 computer and information sciences, 01 natural sciences, Graph, Theoretical Computer Science, Combinatorics, Computational Theory and Mathematics, 010201 computation theory & mathematics, TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY, FOS: Mathematics, Mathematics - Combinatorics, Discrete Mathematics and Combinatorics, Combinatorics (math.CO), 0101 mathematics, business, Computer Science - Discrete Mathematics, Subdivision, Mathematics, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract

A {\em net} is a graph consisting of a triangle $C$ and three more vertices, each of degree one and with its neighbour in $C$, and all adjacent to different vertices of $C$. We give a polynomial-time algorithm to test whether an input graph has an induced subgraph which is a subdivision of a net. Unlike many similar questions, this does not seem to be solvable by an application of the "three-in-a-tree" subroutine.

Published
2013
Full Text
View/download PDF

47. Detecting 2-joins faster

Author

Michel Habib, Kristina Vušković, Nicolas Trotignon, Pierre Charbit, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), School of Computing [Leeds], University of Leeds, École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Trotignon, Nicolas, and École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)

Subjects
FOS: Computer and information sciences, Speedup, Computer science, 010102 general mathematics, Joins, 2-Join, 0102 computer and information sciences, 01 natural sciences, Graph, Theoretical Computer Science, Vertex (geometry), Combinatorics, Detection, Computational Theory and Mathematics, 010201 computation theory & mathematics, Computer Science - Data Structures and Algorithms, Bipartite graph, Discrete Mathematics and Combinatorics, Data Structures and Algorithms (cs.DS), 05C85, 0101 mathematics, ComputingMilieux_MISCELLANEOUS, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract

2-joins are edge cutsets that naturally appear in the decomposition of several classes of graphs closed under taking induced subgraphs, such as balanced bipartite graphs, even-hole-free graphs, perfect graphs and claw-free graphs. Their detection is needed in several algorithms, and is the slowest step for some of them. The classical method to detect a 2-join takes $O(n^3m)$ time where $n$ is the number of vertices of the input graph and $m$ the number of its edges. To detect \emph{non-path} 2-joins (special kinds of 2-joins that are needed in all of the known algorithms that use 2-joins), the fastest known method takes time $O(n^4m)$. Here, we give an $O(n^2m)$-time algorithm for both of these problems. A consequence is a speed up of several known algorithms.

Published
2012

48. The chromatic gap and its extremes

Author

András Gyárfás, Nicolas Trotignon, András Sebö, Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences (MTA), Optimisation Combinatoire (G-SCOP_OC), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), European Project, and École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)

Subjects
Ramsey graphs, 0102 computer and information sciences, 01 natural sciences, Theoretical Computer Science, Combinatorics, [SPI]Engineering Sciences [physics], Computer Science::Discrete Mathematics, Exact formula, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Chromatic scale, 0101 mathematics, ComputingMilieux_MISCELLANEOUS, Mathematics, Mathematics::Combinatorics, 010102 general mathematics, Ramsey theory, Chromatic number, Graph, Clique number, Computational Theory and Mathematics, 010201 computation theory & mathematics, Physics::Accelerator Physics, Ramsey's theorem, Combinatorics (math.CO), Computational problem
Abstract

The {\em chromatic gap} is the difference between the chromatic number and the clique number of a graph. Here we investigate $\gap(n)$, the maximum chromatic gap over graphs on $n$ vertices. Can the extremal graphs be explored? While computational problems related to the chromatic gap are hopeless, an interplay between Ramsey theory and matching theory leads to a simple and (almost) exact formula for $\gap(n)$ in terms of Ramsey numbers., Comment: 41 pages; Cahiers Leibniz No 184, https://consult-cahiersleibniz.g-scop.grenoble-inp.fr/apps/WebObjects/CahiersLeibniz/

Published
2012

49. Graphs that do not contain a cycle with a node that has at least two neighbors on it

Author

Kristina Vušković, Nicolas Trotignon, Marko Radovanović, Pierre Aboulker, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), School of Computing [Leeds], University of Leeds, École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Trotignon, Nicolas, Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-École normale supérieure - Lyon (ENS Lyon)

Subjects
Discrete mathematics, FOS: Computer and information sciences, Discrete Mathematics (cs.DM), General Mathematics, 010102 general mathematics, Induced subgraph, 0102 computer and information sciences, 01 natural sciences, Combinatorics, 010201 computation theory & mathematics, FOS: Mathematics, Mathematics - Combinatorics, 05C75, Node (circuits), Combinatorics (math.CO), 0101 mathematics, Recognition algorithm, Time complexity, ComputingMilieux_MISCELLANEOUS, Decomposition theorem, Mathematics, MathematicsofComputing_DISCRETEMATHEMATICS, Computer Science - Discrete Mathematics
Abstract

We recall several known results about minimally 2-connected graphs, and show that they all follow from a decomposition theorem. Starting from an analogy with critically 2-connected graphs, we give structural characterizations of the classes of graphs that do not contain as a subgraph and as an induced subgraph, a cycle with a node that has at least two neighbors on the cycle. From these characterizations we get polynomial time recognition algorithms for these classes, as well as polynomial time algorithms for vertex-coloring and edge-coloring.

Published
2012

50. Combinatorial Optimization With 2-Joins

Author

Nicolas Trotignon, Kristina Vušković, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), School of Computing [Leeds], University of Leeds, and École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)

Subjects
FOS: Computer and information sciences, Combinatorial optimization, Discrete Mathematics (cs.DM), Perfect graphs, Joins, A* search algorithm, 2-Join, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Maximum clique, Berge graphs, 01 natural sciences, law.invention, Theoretical Computer Science, Combinatorics, Even-hole-free graphs, Skew partition, law, Line graph, FOS: Mathematics, Coloring, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, 0101 mathematics, Time complexity, ComputingMilieux_MISCELLANEOUS, Mathematics, Decomposition, Minimum stable set, 010102 general mathematics, Structure, 05C17, Computational Theory and Mathematics, 010201 computation theory & mathematics, Independent set, Bipartite graph, Combinatorics (math.CO), Computer Science - Discrete Mathematics, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract

International audience; A 2-join is an edge cutset that naturally appears in decomposition of several classes of graphs closed under taking induced sub-graphs, such as perfect graphs and claw-free graphs. In this paper we construct combinatorial polynomial time algorithms for finding a maximum weighted clique, a maximum weighted stable set and an optimal coloring for a class of perfect graphs decomposable by 2-joins: the class of perfect graphs that do not have a balanced skew partition, a 2-join in the complement, nor a homogeneous pair. The techniques we develop are general enough to be easily applied to finding a maximum weighted stable set for another class of graphs known to be decomposable by 2-joins, namely the class of even-hole-free graphs that do not have a star cutset.We also give a simple class of graphs decomposable by 2-joins into bipartite graphs and line graphs, and for which finding a maximum stable set is NP-hard. This shows that having holes all of the same parity gives essential properties for the use of 2-joins in computing stable sets

Published
2012

Catalog

Books, media, physical & digital resources
See catalog results