Nicolas Trotignon
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Nicolas Trotignon has a total of 11 co-authors. Here are the top co-authors by number of shared publications:
- Maria Chudnovsky
Mathematics Department, Princeton University, Princeton, NJ 08544 USA
2 shared publications - Alex Scott
Mathematical Institute University of Oxford Oxford UK
1 shared publication Alexander Scott
1 shared publication- Benjamin Lévêque
Département MIAp LIRMM Université Montpellier 2 CNRS Université Paul-Valéry Montpellier 3
1 shared publication - Frédéric Maffray
G-SCOP_OC - Optimisation Combinatoire (46 Avenue Félix Viallet 38001 GRENOBLE Cedex 1 - France)
1 shared publication Irena Penev
Park Tudor School 46240 Indianapolis IN USA
1 shared publication
Latest Publications
- Open Access
Vertex elimination orderings for hereditary graph classes
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.
Open AccessVertex elimination orderings for hereditary graph classes
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.
- Open AccessOn graphs with no induced subdivision of $K_4$We prove a decomposition theorem for graphs that do not contain a subdivision of $K_4$ as an induced subgraph where $K_4$ is the complete graph on four vertices. We obtain also a structure theorem for the class $\cal C$ of graphs that contain neither a subdivision of $K_4$ nor a wheel as an induced subgraph, where a wheel is a cycle on at least four vertices together with a vertex that has at least three neighbors on the cycle. Our structure theorem is used to prove that every graph in $\cal C$ is 3-colorable and entails a polynomial-time recognition algorithm for membership in $\cal C$. As an intermediate result, we prove a structure theorem for the graphs whose cycles are all chordless.Open AccessOn graphs with no induced subdivision of $K_4$We prove a decomposition theorem for graphs that do not contain a subdivision of $K_4$ as an induced subgraph where $K_4$ is the complete graph on four vertices. We obtain also a structure theorem for the class $\cal C$ of graphs that contain neither a subdivision of $K_4$ nor a wheel as an induced subgraph, where a wheel is a cycle on at least four vertices together with a vertex that has at least three neighbors on the cycle. Our structure theorem is used to prove that every graph in $\cal C$ is 3-colorable and entails a polynomial-time recognition algorithm for membership in $\cal C$. As an intermediate result, we prove a structure theorem for the graphs whose cycles are all chordless.
- Open Access
Combinatorial optimization with 2-joins
A 2-join is an edge cutset that naturally appears in decomposition of several classes of graphs closed under taking induced subgraphs, 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.
Open AccessCombinatorial optimization with 2-joins
A 2-join is an edge cutset that naturally appears in decomposition of several classes of graphs closed under taking induced subgraphs, 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.
- Open Access
Excluding induced subdivisions of the bull and related graphs
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.Open AccessExcluding induced subdivisions of the bull and related graphs
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. - Open Access
Substitution and $χ$-Boundedness
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.Open AccessSubstitution and $χ$-Boundedness
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.