73 citations · 427 across the 49 of their papers we have counts for
5 papers · 1 filter
Tight Bounds on the Clique Chromatic Number
Gwenaël Joret, Piotr Micek, Bruce Reed +1
The clique chromatic number of a graph is the minimum number of colours needed to colour its vertices so that no inclusion-wise maximal clique which is not an isolated vertex is mo…
Erdős-Hajnal properties for powers of sparse graphs
Marcin Briański, Piotr Micek, Michał Pilipczuk +1
We prove that for every nowhere dense class of graphs , positive integer , and , the following holds: in every -vertex graph from $\mathcal{C}…
Enumerating minimal dominating sets in the (in)comparability graphs of bounded dimension posets
Marthe Bonamy, Oscar Defrain, Piotr Micek +1
Enumerating minimal transversals in a hypergraph is a notoriously hard problem. It can be reduced to enumerating minimal dominating sets in a graph, in fact even to enumerating min…
Adjacency Labelling for Planar Graphs (and Beyond)
Vida Dujmović, Louis Esperet, Gwenaël Joret +3
We show that there exists an adjacency labelling scheme for planar graphs where each vertex of an -vertex planar graph is assigned a -bit label and the lab…
Excluding a ladder
Tony Huynh, Gwenaël Joret, Piotr Micek +2
A ladder is a grid graph. When does a graph class exclude some ladder as a minor? We show that this is the case if and only if all graphs in $\mathca…