Source author record

Frédéric Maffray

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

ResearcherUnclaimed source record

math.CO Discrete Mathematics

Catalog footprint

Research overview

22works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Coloring rings

A ring is a graph $R$ whose vertex set can be partitioned into $k \geq 4$ nonempty sets, $X_1, \dots, X_k$ , such that for all $i \in \{1,\dots,k\}$ , the set $X_i$ can be ordered as $X_i = \{u_i^1, \dots, u_i^{|X_i|}\}$ so that $X_i \subseteq N_R[u_i^{|X_i|}] \subseteq \dots \subseteq N_R[u_i^1] = X_{i-1} \cup X_i \cup X_{i+1}$ . A hyperhole is a ring $R$ such that for all $i \in \{1,\dots,k\}$ , $X_i$ is complete to $X_{i-1}\cup X_{i+1}$ . In this paper, we prove that the chromatic number of a ring $R$ is equal to the maximum chromatic number of a hyperhole in $R$ . Using this result, we give a polynomial-time coloring algorithm for rings. Rings formed one of the basic classes in a decomposition theorem for a class of graphs studied by Boncompagni, Penev, and Vušković in [Journal of Graph Theory 91 (2019), 192--246]. Using our coloring algorithm for rings, we show that graphs in this larger class can also be colored in polynomial time. Furthermore, we find the optimal $χ$ -bounding function for this larger class of graphs, and we also verify Hadwiger's conjecture for it.

preprint2016arXiv

$χ$ -bounded families of oriented graphs

A famous conjecture of Gyárfás and Sumner states for any tree $T$ and integer $k$ , if the chromatic number of a graph is large enough, either the graph contains a clique of size $k$ or it contains $T$ as an induced subgraph. We discuss some results and open problems about extensions of this conjecture to oriented graphs. We conjecture that for every oriented star $S$ and integer $k$ , if the chromatic number of a digraph is large enough, either the digraph contains a clique of size $k$ or it contains $S$ as an induced subgraph. As an evidence, we prove that for any oriented star $S$ , every oriented graph with sufficiently large chromatic number contains either a transitive tournament of order $3$ or $S$ as an induced subdigraph. We then study for which sets ${\cal P}$ of orientations of $P_4$ (the path on four vertices) similar statements hold. We establish some positive and negative results.

preprint2016arXiv

4-coloring ( $P_6$ , bull)-free graphs

We present a polynomial-time algorithm that determines whether a graph that contains no induced path on six vertices and no bull (the graph with vertices a, b, c, d, e and edges ab, bc, cd, be, ce) is 4-colorable. We also show that for any fixed k the k-coloring problem can be solved in polynomial time in the class of ( $P_6$ , bull, gem)-free graphs.

preprint2016arXiv

Long induced paths in graphs

We prove that every 3-connected planar graph on $n$ vertices contains an induced path on $Ω(\log n)$ vertices, which is best possible and improves the best known lower bound by a multiplicative factor of $\log \log n$ . We deduce that any planar graph (or more generally, any graph embeddable on a fixed surface) with a path on $n$ vertices, also contains an induced path on $Ω(\sqrt{\log n})$ vertices. We conjecture that for any $k$ , there is a contant $c(k)$ such that any $k$ -degenerate graph with a path on $n$ vertices also contains an induced path on $Ω((\log n)^{c(k)})$ vertices. We provide examples showing that this order of magnitude would be best possible (already for chordal graphs), and prove the conjecture in the case of interval graphs.

preprint2016arXiv

The maximum weight stable set problem in $(P_6,\mbox{bull})$-free graphs

We present a polynomial-time algorithm that finds a maximum weight stable set in a graph that does not contain as an induced subgraph an induced path on six vertices or a bull (the graph with vertices $a, b, c, d, e$ and edges $ab, bc, cd, be, ce$ ).

preprint2015arXiv

Equitable partition of graphs into induced forests

An equitable partition of a graph $G$ is a partition of the vertex-set of $G$ such that the sizes of any two parts differ by at most one. We show that every graph with an acyclic coloring with at most $k$ colors can be equitably partitioned into $k-1$ induced forests. We also prove that for any integers $d\ge 1$ and $k\ge 3^{d-1}$ , any $d$ -degenerate graph can be equitably partitioned into $k$ induced forests. Each of these results implies the existence of a constant $c$ such that for any $k \ge c$ , any planar graph has an equitable partition into $k$ induced forests. This was conjectured by Wu, Zhang, and Li in 2013.

preprint2015arXiv

Even pairs in square-free Berge graphs with no odd prism

We consider the class of Berge graphs that contain no odd prism and no square (cycle on four vertices). We prove that every graph G in this class either is a clique or has an even pair, as conjectured by Everett and Reed. This result is used to devise a polynomial-time algorithm to color optimally every graph in this class.

preprint2015arXiv

Graphs with no induced wheel or antiwheel

A wheel is a graph that consists of a chordless cycle of length at least 4 plus a vertex with at least three neighbors on the cycle. It was shown recently that detecting induced wheels is an NP-complete problem. In contrast, it is shown here that graphs that contain no wheel and no antiwheel have a very simple structure and consequently can be recognized in polynomial time.

preprint2015arXiv

On the b-chromatic number of the Cartesian product of two complete graphs

A b-coloring of a graph $G$ is a coloring of its vertices such that every color class contains a vertex that has neighbors in all other classes. The b-chromatic number of $G$ is the largest integer $k$ such that $G$ has a b-coloring with $k$ colors. Javadi and Omoomi ("On b-coloring of cartesian product of graphs", Ars Combinatoria 107 (2012) 521-536) proved that the b-chromatic number of $K_n \times K_n$ (the Cartesian product of two complete graphs on $n$ vertices) is in the set $\{2n-3, 2n-2\}$ and conjectured that the exact value is $2n-3$ for all $n \ge 5$ . We give counterexamples to this conjecture for $n=5$ , $n=6$ and $n=7$ .

preprint2015arXiv

On the choosability of claw-free perfect graphs

It has been conjectured that for every claw-free graph $G$ the choice number of $G$ is equal to its chromatic number. We focus on the special case of this conjecture where $G$ is perfect. Claw-free perfect graphs can be decomposed via clique-cutset into two special classes called elementary graphs and peculiar graphs. Based on this decomposition we prove that the conjecture holds true for every claw-free perfect graph with maximum clique size at most $4$ .

preprint2014arXiv

On color-critical ( $P_{5},\overline{P}_5$ )-free graphs

A graph is $k$ -critical if it is $k$ -chromatic but each of its proper induced subgraphs is ( $k-1$ )-colorable. It is known that the number of $4$ -critical $P_5$ -free graphs is finite, but there is an infinite number of $k$ -critical $P_5$ -free graphs for each $k \geq 5$ . We show that the number of $k$ -critical $(P_5, \overline{P}_5)$ -free graphs is finite for every fixed $k$ . Our result implies the existence of a certifying algorithm for $k$ -coloring $(P_5, \overline{P}_5)$ -free graphs.

preprint2013arXiv

A class of perfectly contractile graphs

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\'ı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 ${\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.

preprint2013arXiv

Algorithms for perfectly contractile graphs

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

preprint2013arXiv

Algorithms for square- $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(n^{7})$ to find a clique of maximum weight in such a graph. We also consider several subgraph-detection problems related to this class.

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

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 $\{K_1, K_2\}$ such that every induced path from $K_1$ to $K_2$ with no interior vertex in $K_1 \cup K_2$ has odd length. We conjecture that for every Berge graph $G$ on at least two vertices, either one of $G, \bar{G}$ has an even pair, or one of $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.

preprint2013arXiv

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

preprint2013arXiv

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

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.

preprint2012arXiv

Fire Containment in Planar Graphs

In a graph $G$ , a fire starts at some vertex. At every time step, firefighters can protect up to $k$ vertices, and then the fire spreads to all unprotected neighbours. The $k$ -surviving rate $ρ_k(G)$ of $G$ is the expectation of the proportion of vertices that can be saved from the fire, if the starting vertex of the fire is chosen uniformly at random. For a given class of graphs $\cG$ we are interested in the minimum value $k$ such that $ρ_k(G)\geε$ for some constant $ε>0$ and all $G\in\cG$ i.e., such that linearly many vertices are expected to be saved in every graph from $\cG$). In this note, we prove that for planar graphs this minimum value is at most 4, and that it is precisely 2 for triangle-free planar graphs.

preprint2010arXiv

A characterization of b-perfect graphs

A b-coloring is a coloring of the vertices of a graph such that each color class contains a vertex that has a neighbor in all other color classes, and the b-chromatic number of a graph $G$ is the largest integer $k$ such that $G$ admits a b-coloring with $k$ colors. A graph is b-perfect if the b-chromatic number is equal to the chromatic number for every induced subgraph of $G$ . We prove that a graph is b-perfect if and only if it does not contain as an induced subgraph a member of a certain list of twenty-two graphs. This entails the existence of a polynomial-time recognition algorithm and of a polynomial-time algorithm for coloring exactly the vertices of every b-perfect graph.

preprint2006arXiv

Erratum : MCColor is not optimal on Meyniel graphs

A Meyniel graph is a graph in which every odd cycle of length at least five has two chords. In the manuscript "Coloring Meyniel graphs in linear time" we claimed that our algorithm MCColor produces an optimal coloring for every Meyniel graph. But later we found a mistake in the proof and a couterexample to the optimality, which we present here. MCColor can still be used to find a stable set that intersects all maximal cliques of a Meyniel graph in linear time. Consequently it can be used to find an optimal coloring in time O(nm), and the same holds for Algorithm MCS+Color. This is explained in the manuscript "A linear algorithm to find a strong stable set in a Meyniel graph" but this is equivalent to Hertz's algorithm. The current best algorithm for coloring Meyniel graphs is the O(n^2) algorithm LexColor due to Roussel and Rusu. The question of finding a linear-time algorithm to color Meyniel graphs is still open.

preprint2005arXiv

Precoloring co-Meyniel graphs

The pre-coloring extension problem consists, given a graph $G$ and a subset of nodes to which some colors are already assigned, in finding a coloring of $G$ with the minimum number of colors which respects the pre-coloring assignment. This can be reduced to the usual coloring problem on a certain contracted graph. We prove that pre-coloring extension is polynomial for complements of Meyniel graphs. We answer a question of Hujter and Tuza by showing that ``PrExt perfect'' graphs are exactly the co-Meyniel graphs, which also generalizes results of Hujter and Tuza and of Hertz. Moreover we show that, given a co-Meyniel graph, the corresponding contracted graph belongs to a restricted class of perfect graphs (``co-Artemis'' graphs, which are ``co-perfectly contractile'' graphs), whose perfectness is easier to establish than the strong perfect graph theorem. However, the polynomiality of our algorithm still depends on the ellipsoid method for coloring perfect graphs.

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.

Frédéric Maffray

Research overview

Is this your work?

22 publications

Coloring rings

$χ$ -bounded families of oriented graphs

4-coloring ( $P_6$ , bull)-free graphs

Long induced paths in graphs

The maximum weight stable set problem in $(P_6,\mbox{bull})$-free graphs

Equitable partition of graphs into induced forests

Even pairs in square-free Berge graphs with no odd prism

Graphs with no induced wheel or antiwheel

On the b-chromatic number of the Cartesian product of two complete graphs

On the choosability of claw-free perfect graphs

On color-critical ( $P_{5},\overline{P}_5$ )-free graphs

A class of perfectly contractile graphs

Algorithms for perfectly contractile graphs

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

Detecting induced subgraphs

Odd pairs of cliques

On graphs with no induced subdivision of $K_4$

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

Fire Containment in Planar Graphs

A characterization of b-perfect graphs

Erratum : MCColor is not optimal on Meyniel graphs

Precoloring co-Meyniel graphs

See the researcher in context

Building this map preview

Frédéric Maffray

Research overview

Is this your work?

22 publications

Coloring rings

χχχ-bounded families of oriented graphs

4-coloring (P6P_6P6​, bull)-free graphs

Long induced paths in graphs

The maximum weight stable set problem in $(P_6,\mbox{bull})$-free graphs

Equitable partition of graphs into induced forests

Even pairs in square-free Berge graphs with no odd prism

Graphs with no induced wheel or antiwheel

On the b-chromatic number of the Cartesian product of two complete graphs

On the choosability of claw-free perfect graphs

On color-critical (P5,P‾5P_{5},\overline{P}_5P5​,P5​)-free graphs

A class of perfectly contractile graphs

Algorithms for perfectly contractile graphs

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

Detecting induced subgraphs

Odd pairs of cliques

On graphs with no induced subdivision of K4K_4K4​

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

Fire Containment in Planar Graphs

A characterization of b-perfect graphs

Erratum : MCColor is not optimal on Meyniel graphs

Precoloring co-Meyniel graphs

See the researcher in context

Building this map preview

$χ$ -bounded families of oriented graphs

4-coloring ( $P_6$ , bull)-free graphs

On color-critical ( $P_{5},\overline{P}_5$ )-free graphs

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

On graphs with no induced subdivision of $K_4$