BZPEER
More

Discover

About BZPEERSearchGraph

Research tools

HomeCollectionsResearchCollaborationPublish

Network

ExpertsCommunities

Opportunities

Listings

Account

Log inCreate account
Log inCreate account

Source author record

Nicolas Trotignon

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record
math.CODiscrete Mathematicsmath.HOComputational ComplexityData Structures and Algorithms

Catalog footprint

Research overview

35works
5topics
4close collaborators

Actions

Is this your work?

Log in to claim
Open graphBrowse papers

Published work

35 publications

preprint2016arXiv

A decomposition theorem for {ISK4,wheel}-free trigraphs

An ISK4 in a graph G is an induced subgraph of G that is isomorphic to a subdivision of K4 (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. A "trigraph" is a generalization of a graph in which some pairs of vertices have "undetermined" adjacency. We prove a decomposition theorem for {ISK4,wheel}-free trigraphs. Our proof closely follows the proof of a decomposition theorem for ISK4-free graphs due to Lévêque, Maffray, and Trotignon (On graphs with no induced subdivision of K4. J. Combin. Theory Ser. B, 102(4):924-947, 2012).

Open access
preprint2016arXiv

Colouring graphs with constraints on connectivity

A graph GG has maximal local edge-connectivity kk if the maximum number of edge-disjoint paths between every pair of distinct vertices xx and yy is at most kk. We prove Brooks-type theorems for kk-connected graphs with maximal local edge-connectivity kk, and for any graph with maximal local edge-connectivity 3. We also consider several related graph classes defined by constraints on connectivity. In particular, we show that there is a polynomial-time algorithm that, given a 3-connected graph GG with maximal local connectivity 3, outputs an optimal colouring for GG. On the other hand, we prove, for k≥3k \ge 3, that kk-colourability is NP-complete when restricted to minimally kk-connected graphs, and 3-colourability is NP-complete when restricted to (k−1)(k-1)-connected graphs with maximal local connectivity kk. Finally, we consider a parameterization of kk-colourability based on the number of vertices of degree at least k+1k+1, and prove that, even when kk is part of the input, the corresponding parameterized problem is FPT.

Open access
preprint2014arXiv

Isolating highly connected induced subgraphs

We prove that any graph GG of minimum degree greater than 2k2−12k^2-1 has a (k+1)(k+1)-connected induced subgraph HH such that the number of vertices of HH that have neighbors outside of HH is at most 2k2−12k^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 we compute optimal values for the case when k=2k=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.

Open access
preprint2014arXiv

Parameterized algorithm for weighted independent set problem in bull-free graphs

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 kk, when kk 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 kk. 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(k5)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.

Open access
preprint2013arXiv

A class of perfectly contractile graphs

We consider the class A{\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∈AG\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\'ırez-Alfons\'ı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 A{\cal A}. This entails a polynomial-time algorithm, based on successively contracting even pairs, to color optimally every graph in A{\cal A}. This generalizes several results concerning some classical families of perfect graphs.

Open access
preprint2013arXiv

A structure theorem for graphs with no cycle with a unique chord and its consequences

We give a structural description of the class C\cal C of graphs that do not contain a cycle with a unique chord as an induced subgraph. Our main theorem states that any connected graph in C\cal C is either in some simple basic class or has a decomposition. Basic classes are chordless cycles, cliques, bipartite graphs with one side containing only nodes of degree two and induced subgraphs of the famous Heawood or Petersen graph. Decompositions are node cutsets consisting of one or two nodes and edge cutsets called 1-joins. Our decomposition theorem actually gives a complete structure theorem for C{\cal C}, i.e. every graph in C{\cal C} can be built from basic graphs that can be explicitly constructed, and gluing them together by prescribed composition operations; and all graphs built this way are in C{\cal C}. This has several consequences: an O(nm){\cal O}(nm)-time algorithm to decide whether a graph is in C\cal C, an O(n+m){\cal O}(n+m)-time algorithm that finds a maximum clique of any graph in C\cal C and an O(nm){\cal O}(nm)-time coloring algorithm for graphs in C\cal C. We prove that every graph in C\cal C is either 3-colorable or has a coloring with ωω colors where ωω is the size of a largest clique. The problem of finding a maximum stable set for a graph in C\cal C is known to be NP-hard.

Open access
preprint2013arXiv

Algorithms for perfectly contractile graphs

We consider the class A{\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 A′{\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∈AG\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\'ırez-Alfons\'ın and B.A. Reed, eds., Wiley Interscience, 2001]. The analogous conjecture concerning graphs in A′{\cal A}' is still open.

Open access
preprint2013arXiv

Algorithms for square-3PC(⋅,⋅)3PC(\cdot, \cdot)-free Berge graphs

We consider the class of graphs containing no odd hole, no odd antihole, and no configuration consisting of three paths between two nodes such that any two of the paths induce a hole, and at least two of the paths are of length 2. This class generalizes claw-free Berge graphs and square-free Berge graphs. We give a combinatorial algorithm of complexity O(n7)O(n^{7}) to find a clique of maximum weight in such a graph. We also consider several subgraph-detection problems related to this class.

Open access
preprint2013arXiv

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 access
preprint2013arXiv

Complements of nearly perfect graphs

A class of graphs closed under taking induced subgraphs is χχ-bounded if there exists a function ff such that for all graphs GG in the class, χ(G)≤f(ω(G))χ(G) \leq f(ω(G)). We consider the following question initially studied in [A. Gy{á}rf{á}s, Problems from the world surrounding perfect graphs, {\em Zastowania Matematyki Applicationes Mathematicae}, 19:413--441, 1987]. For a χχ-bounded class C\cal C, is the class Cˉ\bar{C} χχ-bounded (where Cˉ\bar{\cal C} is the class of graphs formed by the complements of graphs from C\cal C)? We show that if C\cal C is χχ-bounded by the constant function f(x)=3f(x)=3, then Cˉ\bar{\cal C} is χχ-bounded by g(x)=⌊85x⌋g(x)=\lfloor\frac{8}{5}x\rfloor and this is best possible. We show that for every constant c>0c>0, if C\cal C is χχ-bounded by a function ff such that f(x)=xf(x)=x for x≥cx \geq c, then Cˉ\bar{\cal C} is χχ-bounded. For every jj, we construct a class of graphs χχ-bounded by f(x)=x+x/log⁡j(x)f(x)=x+x/\log^j(x) whose complement is not χχ-bounded.

Open access
preprint2013arXiv

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

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 K4K_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.

Open access
preprint2013arXiv

Decomposing Berge graphs and detecting balanced skew partitions

A hole in a graph is an induced cycle on at least four vertices. A graph is Berge if it has no odd hole and if its complement has no odd hole. In 2002, Chudnovsky, Robertson, Seymour and Thomas proved a decomposition theorem for Berge graphs saying that every Berge graph either is in a well understood basic class, or has some kind of decomposition. Then, Chudnovsky proved stronger theorems. One of them restricts the allowed decompositions to 2-joins and balanced skew partitions. We prove that the problem of deciding whether a graph has a balanced skew partition is NP-hard. We give an O(n9)O(n^9)-time algorithm for the same problem restricted to Berge graphs. Our algorithm is not constructive: it only certifies whether a graph has a balanced skew partition or not. It relies on a new decomposition theorem for Berge graphs that is more precise than the previously known theorems. 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 theorems of Chudnovsky.

Open access
preprint2013arXiv

Detecting 2-joins faster

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(n3m)O(n^3m) time where nn is the number of vertices of the input graph and mm 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(n4m)O(n^4m). Here, we give an O(n2m)O(n^2m)-time algorithm for both of these problems. A consequence is a speed up of several known algorithms.

Open access
preprint2013arXiv

Detecting induced subgraphs

An \emph{s-graph} is a graph with two kinds of edges: \emph{subdivisible} edges and \emph{real} edges. A \emph{realisation} of an s-graph BB is any graph obtained by subdividing subdivisible edges of BB into paths of arbitrary length (at least one). Given an s-graph BB, we study the decision problem ΠBΠ_B whose instance is a graph GG and question is "Does GG contain a realisation of BB as an induced subgraph?". For several BB's, the complexity of ΠBΠ_B is known and here we give the complexity for several more. Our NP-completeness proofs for ΠBΠ_B's rely on the NP-completeness proof of the following problem. Let S\cal S be a set of graphs and dd be an integer. Let ΓSdΓ_{\cal S}^d be the problem whose instance is (G,x,y)(G, x, y) where GG is a graph whose maximum degree is at most d, with no induced subgraph in S\cal S and x,y∈V(G)x, y \in V(G) are two non-adjacent vertices of degree 2. The question is "Does GG contain an induced cycle passing through x,yx, y?". Among several results, we prove that Γ∅3Γ^3_{\emptyset} is NP-complete. We give a simple criterion on a connected graph HH to decide whether Γ{H}+∞Γ^{+\infty}_{\{H\}} is polynomial or NP-complete. The polynomial cases rely on the algorithm three-in-a-tree, due to Chudnovsky and Seymour.

Open access
preprint2013arXiv

Edge-colouring and total-colouring chordless graphs

A graph GG is \emph{chordless} if no cycle in GG 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Δ\geq 3 has chromatic index ΔΔ and total chromatic number Δ+1Δ+ 1. The proofs are algorithmic in the sense that we actually output an optimal colouring of a graph instance in polynomial time.

Open access
preprint2013arXiv

Excluding induced subdivisions of the bull and related graphs

For any graph HH, let Forb∗(H){\rm Forb}^*(H) be the class of graphs with no induced subdivision of HH. 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 HH, there is a function fH:N→Rf_H:\mathbb{N} \rightarrow \mathbb{R} such that for every graph G∈Forb∗(H)G \in {\rm Forb}^*(H), χ(G)≤fH(ω(G))χ(G) \leq f_H(ω(G)). We prove this conjecture for several graphs HH, 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
preprint2013arXiv

Graphes parfaits : structure et algorithmes

This work is the PhD thesis of Nicolas Trotignon, written in 2004 under the supervision of Frédéric Maffray. It is motivated by the desire for a better understanding of perfect graphs. The proof of the Claude Berge's perfect graph conjecture in 2002 by Chudnovsky, Robertson, Seymour and Thomas has shed a new light on this field of combinatorics. But some questions are still unsettled, particulary the existence of a combinatorial algorithm for the coloring of perfect graphs. An even pair of a graph is a pair of vertices such that every path joining them has even length. As proved by Fonlupt and Uhry, the contraction of an even pair preserves the chromatic number, and when applied recursively may lead to an optimal coloring. We prove a conjecture of Everett and Reed saying that this method works for a class of perfect graphs: Artemis graphs. This yields a coloring algorithm for Artemis graphs with complexity O(n2m)O(n^2m). We give an O(n9)O(n^9) algorithm for the recognition of Artemis graphs. Other recognition algorithms are also given, each of them based on subgraph detection routines for Berge graphs. We show that these subgraph detection problems are NP-complete when extended to general graphs.

Open access
preprint2013arXiv

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

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.

Open access
preprint2013arXiv

Linear balanceable and subcubic balanceable graphs

In [{Structural properties and decomposition of linear balanced matrices}, {\it Mathematical Programming}, 55:129--168, 1992], 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 [Balanced Cayley graphs and balanced planar graphs, {\it Discrete Mathematics}, 310:3228--3235, 2010].

Open access
preprint2013arXiv

Odd pairs of cliques

A graph is Berge if it has no induced odd cycle on at least 5 vertices and no complement of induced odd cycle on at least 5 vertices. A graph is perfect if the chromatic number equals the maximum clique number for every induced subgraph. Chudnovsky, Robertson, Seymour and Thomas proved that every Berge graph either falls into some classical family of perfect graphs, or has a structural fault that cannot occur in a minimal imperfect graph. A corollary of this is the strong perfect graph theorem conjectured by Berge: every Berge graph is perfect. An even pair of vertices in a graph is a pair of vertices such that every induced path between them has even length. Meyniel proved that a minimal imperfect graph cannot contain an even pair. So even pairs may be considered as a structural fault. Chudnovsky et al. do not use them, and it is known that some classes of Berge graph have no even pairs. The aim of this work is to investigate an "even-pair-like" notion that could be a structural fault present in every Berge graph. An odd pair of cliques is a pair of cliques {K1,K2}\{K_1, K_2\} such that every induced path from K1K_1 to K2K_2 with no interior vertex in K1∪K2K_1 \cup K_2 has odd length. We conjecture that for every Berge graph GG on at least two vertices, either one of G,GˉG, \bar{G} has an even pair, or one of G,GˉG, \bar{G} has an odd pair of cliques. We conjecture that a minimal imperfect graph has no odd pair of maximal cliques. We prove these conjectures in some special cases. We show that adding all edges between any 2 vertices of the cliques of an odd pair of cliques is an operation that preserves perfectness.

Open access
preprint2013arXiv

On graphs with no induced subdivision of K4K_4

We prove a decomposition theorem for graphs that do not contain a subdivision of K4K_4 as an induced subgraph where K4K_4 is the complete graph on four vertices. We obtain also a structure theorem for the class C\cal C of graphs that contain neither a subdivision of K4K_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 C\cal C is 3-colorable and entails a polynomial-time recognition algorithm for membership in C\cal C. As an intermediate result, we prove a structure theorem for the graphs whose cycles are all chordless.

Open access
preprint2013arXiv

On the structure of self-complementary graphs

A \emph{self-complementary} graph is a graph isomorphic to its complement. An isomorphism between GG and its complement, viewed as a permutation of V(G)V(G), is then called an \emph{antimorphism}. A \emph{skew partition} of GG is a partition of V(G)V(G) into 4 sets A,B,C,DA,B,C,D such that there is no edge between A,BA,B and every possible edge between C,DC,D. A \emph{symmetric partition} of GG is a partition of V(G)V(G) into 4 sets A,B,C,DA,B,C,D such that there is no edge between A,DA, D, no edge between B,CB, C, every possible edge between A,BA,B and every possible edge between C,DC,D. We give a new proof of a theorem of Gibbs saying that every self-complementary graph on 4k4k vertices has kk disjoint paths on 4 vertices as induced subgraph. This new proof gives more structural information than the original one. We conjecture that every self-complementary graph on 4k4k vertices either has an induced cycle on 5 vertices, or a skew partition, or a symmetric partition. The new proof of Gibb's theorem yields a proof of the conjecture for the self-complementary graphs that have an antimorphism that is the product of a two circular permutations, one of them of length 4.

Open access
preprint2013arXiv

Pascal, Fermat et la géométrie du hasard

Ce mémoire réalisé à l'IUFM de Créteil en 1998 sous la direction d'Evelyne Barbin étudie l'histoire du début du calcul des probabilités. Sources: correspondance entre Pascal et Fermat, et Traité du triangle arithmétique de Pascal. -- This report undertaken at the IUFM de Créteil in 1998 under the direction of Evelyne Barbin studies the birth of probability theory. Sources: correspondence between Pascal and Fermat, and Pascal's "Treatise on Arithmetical Triangle"

Open access
preprint2013arXiv

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

We say that a 0-1 matrix NN of size a×ba\times b can be found in a collection of sets H\mathcal{H} if we can find sets H1,H2,…,HaH_{1}, H_{2}, \dots, H_{a} in H\mathcal{H} and elements e1,e2,…,ebe_1, e_2, \dots, e_b in ∪H∈HH\cup_{H \in \mathcal{H}} H such that NN is the incidence matrix of the sets H1,H2,…,HaH_{1}, H_{2}, \dots, H_{a} over the elements e1,e2,…,ebe_1, e_2, \dots, e_b. We prove the following Ramsey-type result: for every n∈Nn\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 nn singletons, or its complementary matrix, or the incidence matrix of a collection of nn 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.

Open access
preprint2013arXiv

Substitution and χχ-Boundedness

A class G\mathcal{G} of graphs is said to be {\em χχ-bounded} if there is a function f:N→Rf:\mathbb{N} \rightarrow \mathbb{R} such that for all G∈GG \in \mathcal{G} and all induced subgraphs HH of GG, χ(H)≤f(ω(H))χ(H) \leq f(ω(H)). In this paper, we show that if G\mathcal{G} is a χχ-bounded class, then so is the closure of G\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 G\mathcal{G} is χχ-bounded by a polynomial (respectively: exponential) function, then the closure of G\mathcal{G} under substitution is also χχ-bounded by some polynomial (respectively: exponential) function. In addition, we show that if G\mathcal{G} is a χχ-bounded class, then the closure of G\mathcal{G} under the operations of gluing along a clique and gluing along a bounded number of vertices together is also χχ-bounded, as is the closure of G\mathcal{G} under the operations of substitution and gluing along a clique together.

Open access
preprint2013arXiv

The kk-in-a-tree problem for graphs of girth at least~kk

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

Open access
preprint2013arXiv

The four-in-a-tree problem in triangle-free graphs

The three-in-a-tree algorithm of Chudnovsky and Seymour decides in time O(n4)O(n^4) 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: what does a triangle-free graph look like if 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)O(nm)-time algorithm that given a triangle-free graph GG together with four vertices outputs either an induced tree that contains them or a partition of V(G)V(G) certifying that no such tree exists. We prove that the problem of deciding whether there exists a tree TT covering the four vertices such that at most one vertex of TT has degree at least 3 is NP-complete.

Open access
preprint2013arXiv

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ć. 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 access

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.