Combinatorics (math.CO)

Abstract: Given two graphs $H_1$ and $H_2$, a graph is $(H_1,H_2)$-free if it contains no induced subgraph isomorphic to $H_1$ and $H_2$. Let $P_t$ be the path on $t$ vertices. A dart is the graph obtained from a diamond by adding a new vertex and making it adjacent to exactly one vertex which degree is 3 in the diamond. In this paper, we show that there are finitely many $k$-vertex-critical $(P_5,dart)$-free graphs for $k \ge 1$. To prove the results we use induction on $k$ and perform a careful structural analysis via Strong Perfect Graph Theorem combined with the pigeonhole principle based on the properties of vertex-critical graphs. Our results imply the existence of a polynomial-time certifying algorithm to decide the $k$-colorability of $(P_5,dart)$-free graphs for $k \ge 1$ where the certificate is either a $k$-coloring or a $(k+1)$-vertex-critical induced subgraph.

Abstract: A $c$-labeling $\phi: V(G) \rightarrow \{1, 2, \hdots, c \}$ of graph $G$ is distinguishing if, for every non-trivial automorphism $\pi$ of $G$, there is some vertex $v$ so that $\phi(v) \neq \phi(\pi(v))$. The distinguishing number of $G$, $D(G)$, is the smallest $c$ such that $G$ has a distinguishing $c$-labeling. We consider a compact version of Tyshkevich's graph decomposition theorem where trivial components are maximally combined to form a complete graph or a graph of isolated vertices. Suppose the compact canonical decomposition of $G$ is $G_{k} \circ G_{k-1} \circ \cdots \circ G_1 \circ G_0$. We prove that $\phi$ is a distinguishing labeling of $G$ if and only if $\phi$ is a distinguishing labeling of $G_i$ when restricted to $V(G_i)$ for $i = 0, \hdots, k$. Thus, $D(G) = \max \{D(G_i), i = 0, \hdots, k \}$. We then present an algorithm that computes the distinguishing number of a unigraph in linear time.

Abstract: Let $\alpha(G)$ denote the cardinality of a maximum independent set, while $\mu(G)$ be the size of a maximum matching in $G=\left( V,E\right) $. It is known that if $\alpha(G)+\mu(G)=\left\vert V\right\vert $, then $G$ is a \textit{K\"{o}nig-Egerv\'{a}ry graph. If $\alpha (G)+\mu(G)=\left\vert V\right\vert -1$, then $G$ is an $1$-K\"{o}nig-Egerv\'{a}ry graph. If $G$ is not a K\"{o}nig-Egerv\'{a}ry graph, and there exists a vertex $v\in V$ (an edge $e\in E$) such that $G-v$ ($G-e$) is K\"{o}nig-Egerv\'{a}ry, then $G$ is called a vertex (an edge) almost K\"{o}nig-Egerv\'{a}ry graph (respectively). In this paper, we characterize all these types of almost K\"{o}nig-Egerv\'{a}ry graphs and present interrelationships between them.

Abstract: In the Maker-Breaker vertex colouring game, first publicised by Gardner in 1981, Maker and Breaker alternately colour vertices of a graph using a fixed palette, maintaining a proper colouring at all times. Maker aims to colour the whole graph, and Breaker aims to make some vertex impossible to colour. We are interested in the following question, first asked by Zhu in 1999: if Maker wins with $k$ colours available, must they also win with $k+1$? This question has remained open, attracting significant attention and being reposed for many similar games. While we cannot resolve this problem for the vertex colouring game, we can answer it in the affirmative for the game of arboricity, resolving a question of Bartnicki, Grytczuk, and Kierstead from 2008. We then consider how one might approach the question of monotonicity for the vertex colouring game, and work with a related game in which the vertices must be coloured in a prescribed order. We demonstrate that this `ordered vertex colouring game' does not have the above monotonicity property, and discuss the implications of this fact to the unordered game. Finally, we provide counterexamples to two open problems concerning a connected version of the graph colouring game.

Abstract: Let $ k $, $ m $ and $ n $ be three positive integers. A $ k $-multiset in $ [n]_m $ ($ m = \infty $ is allowed) is a $ k $-`set' whose elements are integers from $ \cb{1, \ldots, n} $, and each element is allowed to have at most $ m $ repetitions. A family of $ k $-multisets in $ [n]_m $ is called intersecting if every pair of $k$-multisets from the family have non-empty intersection. In this paper, we use a transpositional trick and the Hilton-Milner Theorem to give the size and structure of the largest non-trivial intersecting family of $ k $-multisets in $ [n]_m $.

Abstract: We prove the following variant of the Erd\H{o}s distinct subset sums problem. Given $t \ge 0$ and sufficiently large $n$, every $n$-element set $A$ whose subset sums are distinct modulo $N=2^n+t$ satisfies $$\max A \ge \Big(\frac{1}{3}-o(1)\Big)N.$$ Furthermore, we provide examples showing that the constant $\frac 13$ is best possible. For small values of $t$, we characterise the structure of all sumset-distinct sets modulo $N=2^n+t$ of cardinality $n$.

Abstract: We prove a lower bound on the number of spanning two-forests in a graph, in terms of the number of vertices, edges, and spanning trees. This implies an upper bound on the average cut size of a random two-forest. The main tool is an identity relating the number of spanning trees and two-forests to pairwise effective resistances in a graph. Along the way, we make connections to potential theoretic invariants on metric graphs.

Abstract: The Borsuk conjecture and the V\'azsonyi problem are two attractive and famous questions in discrete and combinatorial geometry, both based on the notion of diameter of a bounded sets. In this paper, we present an equivalence between the critical sets with Borsuk number 4 in $\mathbb{R}^3$ and the minimal structures for the V\'azsonyi problem by using the well-known Reuleaux polyhedra. The latter lead to a full characterization of all finite sets in $\mathbb{R}^3$ with Borsuk number 4. The proof of such equivalence needs various ingredients, in particular, we proved a conjecture dealing with strongly critical configuration for the V\'azsonyi problem and showed that the diameter graph arising from involutive polyhedra is vertex (and edge) 4-critical.