Drawing inspiration from a well-known conjecture of Chvátal on a toughness threshold guaranteeing graph Hamiltonicity, we investigate toughness properties of so-called arbitrarily partitionable (AP) graphs, which are those graphs that can be partitioned into arbitrarily many connected graphs with arbitrary orders, and can be perceived as a weakening of Hamiltonian and traceable graphs. In particular, we provide constructions of non-AP graphs with toughness about 5 4 , i.e. , in which, when removing the vertices of any cut-set S , the number of resulting connected components is at most about 4 5 | S | . We also consider side related questions on graphs that can be partitioned arbitrarily into only a few connected graphs (with arbitrary orders). Among other things, we prove that not all 1-tough graphs can always be partitioned into four connected graphs this way. As going along, we also raise several other questions and problems of interest on the topic.

The 1–2–3 Conjecture asserts that, for every connected graph different from K2, its edges can be labeled with 1,2,3 so that, when coloring each vertex with the sum of its incident labels, no two adjacent vertices get the same color. This conjecture takes place in the more general context of distinguishing labelings, where the goal is to label graphs so that some pairs of their elements are distinguishable relatively to some parameter computed from the labeling. In this work, we investigate the consequences of labeling graphs as in the 1–2–3 Conjecture when it is further required to make the maximum resulting color as small as possible. In some sense, we aim at producing a number of colors that is as close as possible to the chromatic number of the graph. We first investigate the hardness of determining the minimum maximum color by a labeling for a given graph, which we show is NP-complete in the class of bipartite graphs but polynomial-time solvable in the class of graphs with bounded treewidth. We then provide bounds on the minimum maximum color that can be generated both in the general context, and for particular classes of graphs. Finally, we study how using larger labels permit to reduce the maximum color.

Horňak, Przybyło and Woźniak recently proved that, a small class of obvious exceptions apart, every digraph can be 4-arc-weighted so that, for every arc uv⃗, the sum of weights incoming to u is different from the sum of weights outgoing from v. They conjectured a stronger result, namely that the same statement with 3 instead of 4 should also be true. We verify this conjecture in this work. This work takes place in a recent “quest” towards a directed version of the 1–2–3 Conjecture, the variant above being one of the last introduced ones. We take the occasion of this work to establish a summary of all results known in this field, covering known upper bounds, complexity aspects, and choosability. On the way we prove additional results which were missing in the whole picture. We also mention the aspects that remain open.