wovepaper — the arXiv observatory

papers

Publications (4)

math.CO2022

Coloring Square-free Berge Graphs

Maria Chudnovsky, Irene Lo, Frederic Maffray +2

We consider the class of Berge graphs that do not contain a chordless cycle of length $4$ . We present a purely graph-theoretical algorithm that produces an optimal coloring in poly…

cs.DM2019

Square-free graphs with no six-vertex induced path

T. Karthick, Frederic Maffray

We elucidate the structure of $(P_{6}, C_{4})$ -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…

math.CO2019

Coloring graphs with no induced five-vertex path or gem

M. Chudnovsky, T. Karthick, P. Maceli +1

For a graph $G$ , let $I ¨ (G)$ and $I ¨ (G)$ respectively denote the chromatic number and clique number of $G$ . We give an explicit structural description of ( $P_{5}$ ,gem)-free graphs, a…

math.CO2008

Transitive orientations in bull-reducible Berge graphs

Celina de Figueiredo, Frederic Maffray, Claudia Villela Maciel

A bull is a graph with five vertices $r, y, x, z, s$ and five edges $r y$ , $y x$ , $y z$ , $x z$ , $z s$ . A graph $G$ is bull-reducible if no vertex of $G$ lies in two bulls. We prove that…