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 .

We prove that the recognition of exact cubes of trees can be done in polynomial time. More precisely, the exact distance power of a graph is a refinement of the more usual notion of graph power. Given a graph G and a positive integer p , the exact distance p th power of G is the graph G #p on the same vertex set where two vertices are adjacent if their distance is exactly p in G . Recently Bai et al. [Y. Bai, P. P. Cortés, R. Naserasr and D. A. Quiroz. Characterizing and recognizing exact-distance squares of graphs. Discrete Mathematics 347(8). 2024] proved that the recognition of exact squares of trees is polynomially tractable. In order to extend this result to exact cubes of trees, we first test whether there is a caterpillar as an exact cubic root and, if not, proceed with a general tree. Both algorithms rely on the observation that the knowledge of a fixed number of vertices is roughly enough to deduce the whole structure of the tree we aim for.

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.

The ICT4D discipline has faced criticisms of an uneven production of knowledge that reinforces a dichotomy between Global North-Western knowledge systems on the one side, and Global South-indigenous-Southern knowledge systems on the other. As a result, some ICT4D literature has examined the role of the researcher in reinforcing these biases and further exacerbating inequalities, thus highlighting the complex relationship between ICT4D researchers and the research process. Yet, most of this literature has focused on an insider/outsider researcher positionality. This paper explores the role of the researcher from the alternative position of in-betweenness, where researchers adopt more fluid and dynamic positions as reflexive spaces. To do this, we engage in a dialogical process of retrospective reflections based on ICT4D projects in Nigeria, Peru and West Africa. Through these cases, we identify how we experience in-betweenness in distinct ways: as liminal spaces, as performative spaces, and as spaces of disjuncture. We also examine how these forms of in-betweenness informed our research. We demonstrate that a researcher positionality of in-betweenness in ICT4D research can increase awareness of nuanced researcher roles and potentially avoid ethical dilemmas and reproducing biases.

The 2-Decomposition Conjecture, equivalent to the 3-Decomposition Conjecture stated in 2011 by Hoffmann-Ostenhof, claims that every connected graph G with vertices of degree 2 and 3, and satisfying that G - E(C) is disconnected for every cycle C, admits a decomposition into a spanning tree and a matching. In this work we show that the 2-Decomposition Conjecture holds for graphs whose vertices of degree 3 induce a collection of cacti in which each vertex belongs to a cycle.

Given integers $r, k \geq2$ let $\kappa_{r,k+1}(G)$ denote the number of distinct edge colorings of $G$ with $r$ colors, which are $K_{k+1}$-free, i.e., which contain no monochromatic clique on $k+1$ vertices. Alon et al. [ J. Lond. Math. Soc. (2), 70 (2004), pp. 273--288] show that for $r\in\{2,3\}$ and all $k\geq 2$ the maximum of $\kappa_{r,k+1}(G)$ over all $G$ on $n$ vertices is achieved only by the Turán graph, provided $n>n_0(k)$ is sufficiently large. The proof uses Szemerédi's regularity lemma and yields an $n_0(k)$ which is tower type with height exponential in $k$. As a lower bound the authors observed that $n_0(k)$ must be at least exponential in $k$. In this paper we essentially close the gap between the upper and the lower bound for $n_0(k)$. Answering the question posed by Alon et al. we show that the lower bound is of correct order and that it suffices to choose $n_0(k)=\exp(Ck^4)$ for some absolute constant $C$.