56 citations · 715 across the 68 of their papers we have counts for
4 papers · 2 filters
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 . We present a purely graph-theoretical algorithm that produces an optimal coloring in poly…
Perfect graphs of arbitrarily large clique-chromatic number
Pierre Charbit, Irena Penev, Stéphan Thomassé +1
We prove that there exist perfect graphs of arbitrarily large clique-chromatic number. These graphs can be obtained from cobipartite graphs by repeatedly gluing along cliques. This…
Colouring graphs with constraints on connectivity
Pierre Aboulker, Nick Brettell, Frédéric Havet +2
A graph has maximal local edge-connectivity if the maximum number of edge-disjoint paths between every pair of distinct vertices and is at most . We prove Brooks…
The (theta, wheel)-free graphs Part I: only-prism and only-pyramid graphs
Emilie Diot, Marko Radovanović, Nicolas Trotignon +1
Truemper configurations are four types of graphs (namely thetas, wheels, prisms and pyramids) that play an important role in the proof of several decomposition theorems for heredit…