Search

Given a bipartite graph H = (V = VA ∪ VB, E) in which any vertex in VA (resp., VB) has degree at most DA (resp., DB), suppose there is a partition of V that is a refinement of the bipartition VA ∪ VB such that the parts in VA (resp., VB) have size at least KA (resp., kB). We prove that the condition DA/kB + DB/kA ≤ 1 is sufficient for the existence of an independent set of vertices of H that is simultaneously transversal to the partition and show, moreover, that this condition is sharp. This result is a bipartite refinement of two well-known results on independent transversals, one due to the second author and the other due to Szabó and Tardos. [ABSTRACT FROM AUTHOR]

The mean subtree order of a given graph G $G$, denoted μ(G) $\mu (G)$, is the average number of vertices in a subtree of G $G$. Let G $G$ be a connected graph. Chin et al. conjectured that if H $H$ is a proper spanning supergraph of G $G$, then μ(H)>μ(G) $\mu (H)\gt \mu (G)$. Cameron and Mol disproved this conjecture by showing that there are infinitely many pairs of graphs H $H$ and G $G$ with H⊃G $H\supset G$, V(H)=V(G) $V(H)=V(G)$ and |E(H)|=|E(G)|+1 $|E(H)|=|E(G)|+1$ such that μ(H)<μ(G) $\mu (H)\lt \mu (G)$. They also conjectured that for every positive integer k $k$, there exists a pair of graphs G $G$ and H $H$ with H⊃G $H\supset G$, V(H)=V(G) $V(H)=V(G)$, and |E(H)|=|E(G)|+k $|E(H)|=|E(G)|+k$ such that μ(H)<μ(G) $\mu (H)\lt \mu (G)$. Furthermore, they proposed that μ(Km+nK1)<μ(Km,n) $\mu ({K}_{m}+n{K}_{1})\lt \mu ({K}_{m,n})$ provided n≫m $n\gg m$. In this note, we confirm these two conjectures. [ABSTRACT FROM AUTHOR]

List coloring is an influential and classic topic in graph theory. We initiate the study of a natural strengthening of this problem, where instead of one list-coloring, we seek many in parallel. Our explorations have uncovered a potentially rich seam of interesting problems spanning chromatic graph theory. Given a k-list-assignment L of a graph G, which is the assignment of a list L(v) of k colors to each vertex v ∈ V(G), we study the existence of k pairwise-disjoint proper colorings of G using colors from these lists. We may refer to this as a list-packing. Using a mix of combinatorial and probabilistic methods, we set out some basic upper bounds on the smallest k for which such a list-packing is always guaranteed, in terms of the number of vertices, the degeneracy, the maximum degree, or the (list) chromatic number of G. (The reader might already find it interesting that such a minimal k is well defined.) We also pursue a more focused study of the case when G is a bipartite graph. Our results do not yet rule out the tantalising prospect that the minimal k above is not too much larger than the list chromatic number. Our study has taken inspiration from study of the strong chromatic number, and we also explore generalizations of the problem above in the same spirit [ABSTRACT FROM AUTHOR]

A set of vertices in a graph is a Hamiltonian subset if it induces a subgraph containing a Hamiltonian cycle. Kim, Liu, Sharifzadeh, and Staden proved that for large $d$ , among all graphs with minimum degree $d$ , $K_{d+1}$ minimises the number of Hamiltonian subsets. We prove a near optimal lower bound that takes also the order and the structure of a graph into account. For many natural graph classes, it provides a much better bound than the extremal one ( $\approx 2^{d+1}$). Among others, our bound implies that an $n$ -vertex $C_4$ -free graph with minimum degree $d$ contains at least $n2^{d^{2-o(1)}}$ Hamiltonian subsets. [ABSTRACT FROM AUTHOR]

Motivated by a Gan–Loh–Sudakov‐type problem, we introduce the regular Turán numbers, a natural variation on the classical Turán numbers where we restrict ourselves to the class of regular graphs. Among other results, we prove a striking supersaturation version of Mantel's theorem in the case of a regular host graph of odd order. We also characterize the graphs for which the regular Turán numbers behave classically or otherwise. [ABSTRACT FROM AUTHOR]

In 1984, Plesník determined the minimum total distance for given order and diameter and characterized the extremal graphs and digraphs. We prove the analog for given order and radius, when the order is sufficiently large compared to the radius. This confirms asymptotically a conjecture of Chen et al. We also state an analog of the conjecture of Chen et al for digraphs and prove it for sufficiently large order. [ABSTRACT FROM AUTHOR]

Extending the methods of Metrebian (2018), we prove that punctured intervals tile ℤ³. This solves two questions of Metrebian and completely resolves a question of Gruslys, Leader and Tan. We also pose a question that asks whether there is a relation between the genus g (number of holes) in a one-dimensional tile T and a uniform bound d such that T tiles ℤd. An affirmative answer would generalize a conjecture of Gruslys, Leader and Tan (2016). [ABSTRACT FROM AUTHOR]

In this article, we study the so-called rectifying curves in an arbitrary dimensional Euclidean space. A curve is said to be a rectifying curve if, in all points of the curve, the orthogonal complement of its normal vector contains a fixed point. If this fixed point is chosen to be the origin, then this condition is equivalent to saying that the position vector of the curve in every point lies in the orthogonal complement of its normal vector. Here we characterize rectifying curves in the n-dimensional Euclidean space in different ways: using conditions on their curvatures, with an expression for the tangential component, the normal component, or the binormal components of their position vector, and by constructing them starting from an arclength parameterized curve on the unit hypersphere. [ABSTRACT FROM AUTHOR]