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 .

The analogue of Hadwiger’s conjecture for the immersion order states that every graph G contains K X(G) as an immersion. Our work is motivated by a strengthening of this conjecture which asserts that every graph G contains K X(G) as a totally odd immersion. As evidence for this strengthened conjecture and inspired by a result of Steiner (2024), we show that if the chromatic number of G is equal to any of its topological lower bounds, then G contains a totally odd immersion of K [x( G)/2] +1 . Kneser graphs are canonical examples of graphs satisfying such equalities for their chromatic numbers. Simonyi and Zsban (2010) showed that every Kneser graph G with large enough order (compared to x (G) ) contains a totally odd subdivision of K X(G) , thus satisfying the motivating conjecture in a strong sense. We show that, in fact, for every t ≥ 8, there are t -chromatic Kneser graphs that contain arbitrarily large complete totally odd subdivisions.

The counterexamples that Catlin used to disprove Hajós’ conjecture (For every integer t ≥ 0, every graph G with no subdivision of K t+1 is t- colorable.) are the lexicographic product of cliques and cycles. In 1989, Lescure and Meyniel made a conjecture that is a weakening of Hajós’ and that remains open: For every integer t ≥ 0, every graph G with no immersion of K t+1 is t- colorable. Can minimal counterexamples to this conjecture be produced through graph products? Collins, Heenehan, and McDonald recently gave a negative answer to this question for the lexicographic and Cartesian product. We consider a strengthening of the Lescure and Meyniel conjecture, different from that of Hajós, based on the notion of totally odd immersions. We study the largest totally odd immersion appearing in the graph product of two graphs. Our results imply that no minimal counterexample to this strengthened conjecture can be obtained from the Cartesian, lexicographic, direct (tensor) or strong product of graphs.

Abstract. Given two [Formula: see text]-vertex graphs [Formula: see text] and [Formula: see text] of bounded treewidth, is there an [Formula: see text]-vertex graph [Formula: see text] of bounded treewidth having subgraphs isomorphic to [Formula: see text] and [Formula: see text]? Our main result is a negative answer to this question, in a strong sense: we show that the answer is no even if [Formula: see text] is a binary tree and [Formula: see text] is a ternary tree. We also provide an extensive study of cases where such “gluing” is possible. In particular, we prove that if [Formula: see text] has treewidth [Formula: see text] and [Formula: see text] has pathwidth [Formula: see text], then there is an [Formula: see text]-vertex graph of treewidth at most [Formula: see text] containing both [Formula: see text] and [Formula: see text] as subgraphs.

The analogue of Hadwiger’s conjecture for the immersion order states that every graph G contains the complete graph KX(G) as an immersion. Like its minor-order counterpart it is open even for graphs with independence number 2. Let G and H be graphs with independence number at most 2, such that |V(H)| ≤ 4. We show that if G is H-free, then G satisfies the conjecture.

We study the model-checking problem for first- and monadic second-order logic on finite relational structures. The problem of verifying whether a formula of these logics is true on a given structure is considered intractable in general, but it does become tractable on interesting classes of structures, such as on classes whose Gaifman graphs have bounded treewidth. In this article, we continue this line of research and study model-checking for first- and monadic second-order logic in the presence of an ordering on the input structure. We do so in two settings: the general ordered case, where the input structures are equipped with a fixed order or successor relation, and the order-invariant case, where the formulas may resort to an ordering, but their truth must be independent of the particular choice of order. In the first setting we show very strong intractability results for most interesting classes of structures. In contrast, in the order-invariant case we obtain tractability results for order-invariant monadic second-order formulas on the same classes of graphs as in the unordered case. For first-order logic, we obtain tractability of successor-invariant formulas on classes whose Gaifman graphs have bounded expansion. Furthermore, we show that model-checking for order-invariant first-order formulas is tractable on coloured posets of bounded width.

A successor-invariant first-order formula is a formula that has access to an auxiliary successor relation on a structure's universe, but the model relation is independent of the particular interpretation of this relation. It is well known that successor-invariant formulas are more expressive on finite structures than plain first-order formulas without a successor relation. This naturally raises the question whether this increase in expressive power comes at an extra cost to solve the model-checking problem, that is, the problem to decide whether a given structure together with some (and hence every) successor relation is a model of a given formula. It was shown earlier that adding successor-invariance to first-order logic essentially comes at no extra cost for the model-checking problem on classes of finite structures whose underlying Gaifman graph is planar [1], excludes a fixed minor [2] or a fixed topological minor [3], [4]. In this work we show that the model-checking problem for successor-invariant formulas is fixed-parameter tractable on any class of finite structures whose underlying Gaifman graphs form a class of bounded expansion. Our result generalises all earlier results and comes close to the best tractability results on nowhere dense classes of graphs currently known for plain first-order logic.