4 papers · 1 filter
Biclique decompositions from Welzl orders
Jean Cardinal, Rose McCarty, Yelena Yuditsky
A biclique decomposition of a graph is a partition of its edges into complete bipartite subgraphs. We consider graphs whose vertices can be ordered such that the neighborhood of ev…
Compact Representation of Semilinear and Terrain-like Graphs
Jean Cardinal, Yelena Yuditsky
We consider the existence and construction of \textit{biclique covers} of graphs, consisting of coverings of their edge sets by complete bipartite graphs. The \textit{size} of such…
Polynomial Gyárfás-Sumner conjecture for graphs of bounded boxicity
James Davies, Yelena Yuditsky
We prove that for every positive integer and forest , the class of intersection graphs of axis-aligned boxes in with no induced subgraph is (polynomially)…
Counterexamples to Thomassen's conjecture on decomposition of cubic graphs
Thomas Bellitto, Tereza Klimošová, Martin Merker +2
We construct an infinite family of counterexamples to Thomassen's conjecture that the vertices of every 3-connected, cubic graph on at least 8 vertices can be colored blue and red…