1 citations · 1 across the 8 of their papers we have counts for
9 papers · 1 filter
Revisiting a theorem by Folkman on graph colouring
Marthe Bonamy, Pierre Charbit, Oscar Defrain +5
We give a short proof of the following theorem due to Jon H. Folkman (1969): The chromatic number of any graph is at most plus the maximum over all subgraphs of the difference…
Polynomial Cases for the Vertex Coloring Problem
T. Karthick, Frédéric Maffray, Lucas Pastor
The computational complexity of the Vertex Coloring problem is known for all hereditary classes of graphs defined by forbidding two connected five-vertex induced subgraphs, except…
Decomposition techniques applied to the Clique-Stable set Separation problem
Nicolas Bousquet, Aurélie Lagoutte, Frédéric Maffray +1
In a graph, a Clique-Stable Set separator (CS-separator) is a family of cuts (bipartitions of the vertex set) such that for every clique and every stable set …
Maximum Weight Stable Set in (, bull)-free graphs and (, bull)-free graphs
Frédéric Maffray, Lucas Pastor
We give a polynomial time algorithm that finds the maximum weight stable set in a graph that does not contain an induced path on seven vertices or a bull (the graph with vertices $…
Colouring squares of claw-free graphs
Rémi de Joannis de Verclos, Ross J. Kang, Lucas Pastor
Is there some absolute such that for any claw-free graph , the chromatic number of the square of satisfies , where $ω(G)…
The maximum weight stable set problem in $(P_6,\mbox{bull})$-free graphs
Frédéric Maffray, Lucas Pastor
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…
4-coloring (, bull)-free graphs
Frédéric Maffray, Lucas Pastor
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…
Disproving the normal graph conjecture
Ararat Harutyunyan, Lucas Pastor, Stéphan Thomassé
A graph is called normal if there exist two coverings, and of its vertex set such that every member of induces a clique in , every mem…
On the choosability of claw-free perfect graphs
Sylvain Gravier, Frédéric Maffray, Lucas Pastor
It has been conjectured that for every claw-free graph the choice number of is equal to its chromatic number. We focus on the special case of this conjecture where is p…