Take a prime power , an integer , and a coordinate subspace over the Galois field . One can associate with an -partite -uniform clutter , where every part has size and there is a bijection between the vectors in and the members of . In this paper, we …
In 1986, Robertson and Seymour proved a generalization of the seminal result of Erdős and Pósa on the duality of packing and covering cycles: A graph has the Erdős-Pósa property for minor if and only if it is planar. In particular, for every non-planar graph they gave examples showing that the Erdős-Pósa property does …
The square of a graph , denoted , has the same vertex set as and has an edge between two vertices if the distance between them in is at most . Wegner's conjecture (1977) states that for a planar graph , the chromatic number of is at most 7 if $\Delta(G) …
Even delta-matroids generalize matroids, as they are defined by a certain basis exchange axiom weaker than that of matroids. One natural example of even delta-matroids comes from a skew-symmetric matrix over a given field , and we say such an even delta-matroid is representable over the field . Interestingly, a matroid is representable over …
Graph pebbling is a combinatorial game played on an undirected graph with an initial configuration of pebbles. A pebbling move consists of removing two pebbles from one vertex and placing one pebbling on an adjacent vertex. The pebbling number of a graph is the smallest number of pebbles necessary such that, given any initial configuration …