Motivated by different characterizations of planar graphs and the 4-Color Theorem, several structural results concerning graphs of high chromatic number have been obtained. Toward strengthening some of these results, we consider the balanced chromatic number , χ b ( G ˆ ) , of a signed graph G ˆ . This is the minimum number of parts into which the vertices of a signed graph can be partitioned so that none of the parts induces a negative cycle. This extends the notion of the chromatic number of a graph since χ ( G ) = χ b ( G ̃ ) , where G ̃ denotes the signed graph obtained from G by replacing each edge with a pair of (parallel) positive and negative edges. We introduce a signed version of Hadwiger’s conjecture as follows. Conjecture . If a signed graph G ˆ has no negative loop and no K ̃ t -minor, then its balanced chromatic number is at most t − 1 . We prove that this conjecture is, in fact, equivalent to Hadwiger’s conjecture and show its relation to the odd Hadwiger Conjecture. Motivated by these results, we also consider the relation between subdivisions and balanced chromatic number. We prove that if ( G , σ ) has no negative loop and no K ̃ t -subdivision, then it admits a balanced 79 2 t 2 -coloring. This qualitatively generalizes a result of Kawarabayashi (2013) on totally odd subdivisions. Finally, following supportive results in the literature on the fractional variant of Hadwiger’s conjecture, we show that the fractional balanced chromatic number of any signed graph with no positive loop and no K ̃ t -minor is at most 2 t − 2 .

Abstract. Jaeger, Linial, Payan, and Tarsi [ J. Combin. Theory Ser. B, 56 (1992), pp. 165–182] introduced the notion of [Formula: see text]-connectivity for graphs in 1992 and proved a decomposition for cubic graphs from which [Formula: see text]-connectivity follows for all 3-edge-connected graphs when [Formula: see text]. The concept of [Formula: see text]-connectivity was generalized to signed graphs by Li, Luo, Ma, and Zhang in 2018 [ Discrete Math., 341 (2018), pp. 3227–3236] and they proved that all flow-admissible, 4-edge-connected signed graphs are [Formula: see text]-connected when [Formula: see text] and [Formula: see text]. We prove that all flow-admissible, 3-edge-connected signed graphs are [Formula: see text]-connected when [Formula: see text] and [Formula: see text]. Our proof is based on a decomposition that is a signed-graph analogue of the decomposition found by Jaeger et al. and which may be of independent interest.

Tuza conjectured that for every graph $G$ the maximum size $\nu$ of a set of edge-disjoint triangles and minimum size $\tau$ of a set of edges meeting all triangles satisfy $\tau \leq 2\nu$. We consider an edge-weighted version of this conjecture, which amounts to packing and covering triangles in multigraphs. Several known results about the original problem are shown to be true in this context, and some are improved. In particular, we answer a question of Krivelevich, who proved that $\tau \leq 2\nu^*$ (where $\nu^*$ is the fractional version of $\nu$) and asked whether this is tight. We prove that $\tau \leq 2\nu^*-\frac{1}{\sqrt{6}}\sqrt{\nu^*}$ and show that this bound is essentially best possible.