On token signed graphs - Dalfó, C.; Fiol, M. A.; Steffen, Eckhard (arXiv:2403.02924)
We introduce the concept of a k-token signed graph and study some of its combinatorial and algebraic properties. We prove that two switching isomorphic signed graphs have switching isomorphic token graphs. Moreover, we show that the Laplacian spectrum of a balanced signed graph is contained in the Laplacian spectra of its k-token signed graph. Besides, we introduce and study the unbalance level of a signed graph, which is a new parameter that measures how far a signed graph is from being balanced. Moreover, we study the relation between the frustration index and the unbalance level of signed graphs and their token signed graphs.

Edge-Connectivity and Pairwise Disjoint Perfect Matchings in Regular Graphs - Ma, Yulai; Mattiolo, Davide; Steffen, Eckhard; Wolf, Isaak Hieronymus (Combinatorica)
For 0 ≤ t ≤ r let m(t, r) be the maximum number s such that every t-edge-connected r-graph has s pairwise disjoint perfect matchings. There are only a few values of m(t, r) known, for instance m(3, 3) = m(4, r) = 1, and m(t, r) ≤ r − 2 for all t = 5, and m(t, r) ≤ r − 3 if r is even. We prove that m(2l, r) ≤ 3l − 6 for every l ≥ 3 and r ≥ 2l.
Keywords: Computational Mathematics; Discrete Mathematics and Combinatorics

Critically 3-frustrated signed graphs - Cappello, Chiara; Naserasr, Reza; Steffen, Eckhard; Wang, Zhouningxin (arXiv:2304.10243)
Extending the notion of maxcut, the study of the frustration index of signed graphs is one of the basic questions in the theory of signed graphs. Recently two of the authors initiated the study of critically frustrated signed graphs. That is a signed graph whose frustration index decreases with the removal of any edge. The main focus of this study is on critical signed graphs which are not edge-disjoint unions of critically frustrated signed graphs (namely non-decomposable signed graphs) and which are not built from other critically frustrated signed graphs by subdivision. We conjecture that for any given k there are only finitely many critically k-frustrated signed graphs of this kind. Providing support for this conjecture we show that there are only two of such critically 3-frustrated signed graphs where there is no pair of edge-disjoint negative cycles. Similarly, we show that there are exactly ten critically 3-frustrated signed planar graphs that are neither decomposable nor subdivisions of other critically frustrated signed graphs. We present a method for building non-decomposable critically frustrated signed graphs based on two given such signed graphs. We also show that the condition of being non-decomposable is necessary for our conjecture.

Algorithms for the genome median under a restricted measure of rearrangement - Silva, Helmuth O.M.; Rubert, Diego P.; Araujo, Eloi; Steffen, Eckhard; Doerr, Daniel; Martinez, Fábio V. (RAIRO - Operations Research)
Ancestral reconstruction is a classic task in comparative genomics. Here, we study the genome median problem, a related computational problem which, given a set of three or more genomes, asks to find a new genome that minimizes the sum of pairwise distances between it and the given genomes. The distance stands for the amount of evolution observed at the genome level, for which we determine the minimum number of rearrangement operations necessary to transform one genome into the other. For almost all rearrangement operations the median problem is NP-hard, with the exception of the breakpoint median that can be constructed efficiently for multichromosomal circular and mixed genomes. In this work, we study the median problem under a restricted rearrangement measure called c4-distance, which is closely related to the breakpoint and the DCJ distance. We identify tight bounds and decomposers of the c4-median and develop algorithms for its construction, one exact ILP-based and three combinatorial heuristics. Subsequently, we perform experiments on simulated data sets. Our results suggest that the c4-distance is useful for the study the genome median problem, from theoretical and practical perspectives.
Keywords: Management Science and Operations Research; Computer Science Applications; Theoretical Computer Science

Sets of r-graphs that color all r-graphs - Ma, Yulai; Mattiolo, Davide; Steffen, Eckhard; Wolf, Isaak Hieronymus (arXiv:2305.08619)

Pairwise Disjoint Perfect Matchings in r-Edge-Connected r-Regular Graphs - Ma, Yulai; Mattiolo, Davide; Steffen, Eckhard; Wolf, Isaak Hieronymus (SIAM Journal on Discrete Mathematics)
Keywords: General Mathematics

Bounds for the chromatic index of signed multigraphs - Steffen, Eckhard; Wolf, Isaak Hieronymus (Discrete Applied Mathematics)
Keywords: Applied Mathematics; Discrete Mathematics and Combinatorics

Graph-Theoretical Models for the Analysis and Design of Socio-Technical Networks - Cappello, Chiara; Steffen, Eckhard (The Digital Twin of Humans)

Rotation r-graphs - Steffen, Eckhard; Wolf, Isaak Hieronymus (Discrete Mathematics)
Keywords: Discrete Mathematics and Combinatorics; Theoretical Computer Science

The Digital Twin of Humans

Symmetric Set Coloring of Signed Graphs - Cappello, Chiara; Steffen, Eckhard (Annals of Combinatorics)
There are many concepts of signed graph coloring which are defined by assigning colors to the vertices of the graphs. These concepts usually differ in the number of self-inverse colors used. We introduce a unifying concept for this kind of coloring by assigning elements from symmetric sets to the vertices of the signed graphs. In the first part of the paper, we study colorings with elements from symmetric sets where the number of self-inverse elements is fixed. We prove a Brooks’-type theorem and upper bounds for the corresponding chromatic numbers in terms of the chromatic number of the underlying graph. These results are used in the second part where we introduce the symset-chromatic number χsym(G,σ) of a signed graph (G,σ). We show that the symset-chromatic number gives the minimum partition of a signed graph into independent sets and non-bipartite antibalanced subgraphs. In particular, χsym(G,σ)≤χ(G). In the final section we show that these colorings can also be formalized as DP-colorings.
Keywords: Discrete Mathematics and Combinatorics

Frustration-critical signed graphs - Cappello, Chiara; Steffen, Eckhard (Discrete Applied Mathematics)
Keywords: Applied Mathematics; Discrete Mathematics and Combinatorics

Nowhere-zero 3-flows in toroidal graphs - Li, Jiaao; Ma, Yulai; Miao, Zhengke; Shi, Yongtang; Wang, Weifan; Zhang, Cun-Quan (Journal of Combinatorial Theory, Series B)
Keywords: Computational Theory and Mathematics; Discrete Mathematics and Combinatorics; Theoretical Computer Science

On 3-flow-critical graphs - Li, Jiaao; Ma, Yulai; Shi, Yongtang; Wang, Weifan; Wu, Yezhou (European Journal of Combinatorics)
Keywords: Discrete Mathematics and Combinatorics

Measures of Edge-Uncolorability of Cubic Graphs - Fiol, M. A.; Mazzuoccolo, Guiseppe; Steffen, Eckhard (The Electronic Journal of Combinatorics)
There are many hard conjectures in graph theory, like Tutte's 5-flow conjecture, and the 5-cycle double cover conjecture, which would be true in general if they would be true for cubic graphs. Since most of them are trivially true for 3-edge-colorable cubic graphs, cubic graphs which are not 3-edge-colorable, often called snarks, play a key role in this context. Here, we survey parameters measuring how far apart a non 3-edge-colorable graph is from being 3-edge-colorable. We study their interrelation and prove some new results. Besides getting new insight into the structure of snarks, we show that such measures give partial results with respect to these important conjectures. The paper closes with a list of open problems and conjectures.
Keywords: Cubic graph; Tait coloring; Snark; Boole coloring; Berge's conjecture; Tutte's 5-flow conjecture

Cores, joins and the Fano-flow conjectures - Jin, Ligang; Mazzuoccolo, Giuseppe; Steffen, Eckhard (Discussiones Mathematicae Graph Theory)

Approximating Vizing’s independence number conjecture - Steffen, Eckhard (Australasian Journal of Combinatorics)

Nearly nowhere-zero r-flow graphs - Steffen, Eckhard (Discrete Mathematics)