4 papers · 1 filter
Adjacency Labeling Schemes for Small Classes
Édouard Bonnet, Julien Duron, John Sylvester +1
A graph class admits an implicit representation if, for every positive integer , its -vertex graphs have a -bit (adjacency) labeling scheme, i.e., their vertices c…
Sparse Induced Subgraphs of Large Treewidth
Édouard Bonnet
Motivated by an induced counterpart of treewidth sparsifiers (i.e., sparse subgraphs keeping the treewidth large) provided by the celebrated Grid Minor theorem of Robertson and Sey…
Symmetric-Difference (Degeneracy) and Signed Tree Models
Édouard Bonnet, Julien Duron, John Sylvester +1
We introduce a dense counterpart of graph degeneracy, which extends the recently-proposed invariant symmetric difference. We say that a graph has sd-degeneracy (for symmetric-diffe…
Graphs without a 3-connected subgraph are 4-colorable
Édouard Bonnet, Carl Feghali, Tung Nguyen +4
In 1972, Mader showed that every graph without a 3-connected subgraph is 4-degenerate and thus 5-colorable}. We show that the number 5 of colors can be replaced by 4, which is best…