51 citations · 245 across the 35 of their papers we have counts for
39 papers
Coloring rings
Frédéric Maffray, Irena Penev, Kristina Vušković
A ring is a graph whose vertex set can be partitioned into nonempty sets, , such that for all , the set can be ordered as…
Coloring graphs with no induced five-vertex path or gem
M. Chudnovsky, T. Karthick, P. Maceli +1
For a graph , let and respectively denote the chromatic number and clique number of . We give an explicit structural description of (,gem)-free graphs, and…
Square-free graphs with no six-vertex induced path
T. Karthick, Frederic Maffray
We elucidate the structure of -free graphs by showing that every such graph either has a clique cutset, or a universal vertex, or belongs to several special classes of g…
On some Graphs with a Unique Perfect Matching
S. Chaplick, M. Fürst, F. Maffray +1
We show that deciding whether a given graph of size has a unique perfect matching as well as finding that matching, if it exists, can be done in time if is eithe…
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…
Coloring (, bull)-free graphs
Frédéric Maffray
We give a polynomial-time algorithm that computes the chromatic number of any graph that contains no path on five vertices and no bull as an induced subgraph (where the bull is the…