@article{59806, abstract = {{We introduce a model of information dissemination in signed networks. It is a discrete-time process in which uninformed actors incrementally receive information from their informed neighbors or from the outside. Our goal is to minimize the number of confused actors — that is, the number of actors who receive contradictory information. We prove upper bounds for the number of confused actors in signed networks and in equivalence classes of signed networks. In particular, we show that there are signed networks where, for any information placement strategy, almost 60% of the actors are confused. Furthermore, this is also the case when considering the minimum number of confused actors within an equivalence class of signed graphs.}}, author = {{Jin, Ligang and Steffen, Eckhard}}, issn = {{0166-218X}}, journal = {{Discrete Applied Mathematics}}, pages = {{99--106}}, publisher = {{Elsevier BV}}, title = {{{Information dissemination and confusion in signed networks}}}, doi = {{10.1016/j.dam.2025.04.049}}, volume = {{373}}, year = {{2025}}, } @article{59169, abstract = {{An r-regular graph is an r-graph, if every odd set of vertices is connected to its complement by at least r edges. Let G and H be r-graphs. An H-coloring of G is a mapping such that each r adjacent edges of G are mapped to r adjacent edges of H. For every , let be an inclusion-wise minimal set of connected r-graphs, such that for every connected r-graph G there is an which colors G. The Petersen Coloring Conjecture states that consists of the Petersen graph P. We show that if true, then this is a very exclusive situation. Our main result is that either or is an infinite set and if , then is an infinite set. In particular, for all , is unique. We first characterize and then prove that if contains more than one element, then it is an infinite set. To obtain our main result we show that contains the smallest r-graphs of class 2 and the smallest poorly matchable r-graphs, and we determine the smallest r-graphs of class 2.}}, author = {{Ma, Yulai and Mattiolo, Davide and Steffen, Eckhard and Wolf, Isaak H.}}, issn = {{0209-9683}}, journal = {{Combinatorica}}, number = {{2}}, publisher = {{Springer Science and Business Media LLC}}, title = {{{Sets of r-Graphs that Color All r-Graphs}}}, doi = {{10.1007/s00493-025-00144-4}}, volume = {{45}}, year = {{2025}}, } @article{61042, abstract = {{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.}}, author = {{Dalfó, C. and Fiol, M. A. and Steffen, Eckhard}}, issn = {{0925-9899}}, journal = {{Journal of Algebraic Combinatorics}}, number = {{1}}, publisher = {{Springer Science and Business Media LLC}}, title = {{{On token signed graphs}}}, doi = {{10.1007/s10801-025-01416-4}}, volume = {{62}}, year = {{2025}}, } @unpublished{63187, author = {{Kidner, Arnott Jeffery Joel and Steffen, Eckhard and Yu, Weiqiang}}, booktitle = {{arXiv:2512.14285}}, title = {{{Edge-coloring 4- and 5-regular projective planar graphs with no Petersen-minor}}}, year = {{2025}}, } @article{49905, abstract = {{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.}}, author = {{Ma, Yulai and Mattiolo, Davide and Steffen, Eckhard and Wolf, Isaak Hieronymus}}, issn = {{0209-9683}}, journal = {{Combinatorica}}, keywords = {{Computational Mathematics, Discrete Mathematics and Combinatorics}}, pages = {{429--440}}, publisher = {{Springer Science and Business Media LLC}}, title = {{{Edge-Connectivity and Pairwise Disjoint Perfect Matchings in Regular Graphs}}}, doi = {{10.1007/s00493-023-00078-9}}, volume = {{44}}, year = {{2024}}, } @article{56497, author = {{Cappello, Chiara and Naserasr, Reza and Steffen, Eckhard and Wang, Zhouningxin}}, issn = {{0012-365X}}, journal = {{Discrete Mathematics}}, number = {{1}}, publisher = {{Elsevier BV}}, title = {{{Critically 3-frustrated signed graphs}}}, doi = {{10.1016/j.disc.2024.114258}}, volume = {{348}}, year = {{2024}}, } @article{51351, author = {{Steffen, Eckhard and Wolf, Isaak Hieronymus}}, issn = {{0166-218X}}, journal = {{Discrete Applied Mathematics}}, keywords = {{Applied Mathematics, Discrete Mathematics and Combinatorics}}, pages = {{185--189}}, publisher = {{Elsevier BV}}, title = {{{Bounds for the chromatic index of signed multigraphs}}}, doi = {{10.1016/j.dam.2023.05.008}}, volume = {{337}}, year = {{2023}}, } @inbook{45190, author = {{Cappello, Chiara and Steffen, Eckhard}}, booktitle = {{The Digital Twin of Humans}}, isbn = {{9783031261039}}, pages = {{93----110}}, publisher = {{Springer International Publishing}}, title = {{{Graph-Theoretical Models for the Analysis and Design of Socio-Technical Networks}}}, doi = {{10.1007/978-3-031-26104-6_5}}, year = {{2023}}, } @article{51357, author = {{Steffen, Eckhard and Wolf, Isaak Hieronymus}}, issn = {{0012-365X}}, journal = {{Discrete Mathematics}}, keywords = {{Discrete Mathematics and Combinatorics, Theoretical Computer Science}}, publisher = {{Elsevier BV}}, title = {{{Rotation r-graphs}}}, doi = {{10.1016/j.disc.2023.113457}}, year = {{2023}}, } @inbook{45110, author = {{Gräßler, Iris and Steffen, Eckhard and Maier, Günter W. and Roesmann, Daniel}}, booktitle = {{The Digital Twin of Humans}}, editor = {{Gräßler, Iris and Maier, Günter W. and Steffen, Eckhard and Roesmann, Daniel}}, isbn = {{9783031261039}}, pages = {{3--10}}, publisher = {{Springer International Publishing}}, title = {{{Introduction—The Digital Twin of Humans}}}, doi = {{10.1007/978-3-031-26104-6_1}}, year = {{2023}}, } @book{45191, editor = {{Gräßler, Iris and Maier, Günter W. and Steffen, Eckhard and Roesmann, Daniel}}, isbn = {{9783031261039}}, publisher = {{Springer International Publishing}}, title = {{{The Digital Twin of Humans}}}, doi = {{10.1007/978-3-031-26104-6}}, year = {{2023}}, } @article{44857, abstract = {{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.}}, author = {{Silva, Helmuth O.M. and Rubert, Diego P. and Araujo, Eloi and Steffen, Eckhard and Doerr, Daniel and Martinez, Fábio V.}}, issn = {{0399-0559}}, journal = {{RAIRO - Operations Research}}, keywords = {{Management Science and Operations Research, Computer Science Applications, Theoretical Computer Science}}, number = {{3}}, pages = {{1045--1058}}, publisher = {{EDP Sciences}}, title = {{{Algorithms for the genome median under a restricted measure of rearrangement}}}, doi = {{10.1051/ro/2023052}}, volume = {{57}}, year = {{2023}}, } @unpublished{44859, author = {{Ma, Yulai and Mattiolo, Davide and Steffen, Eckhard and Wolf, Isaak Hieronymus}}, booktitle = {{arXiv:2305.08619}}, title = {{{Sets of r-graphs that color all r-graphs}}}, year = {{2023}}, } @article{46256, author = {{Ma, Yulai and Mattiolo, Davide and Steffen, Eckhard and Wolf, Isaak Hieronymus}}, issn = {{0895-4801}}, journal = {{SIAM Journal on Discrete Mathematics}}, keywords = {{General Mathematics}}, number = {{3}}, pages = {{1548--1565}}, publisher = {{Society for Industrial & Applied Mathematics (SIAM)}}, title = {{{Pairwise Disjoint Perfect Matchings in r-Edge-Connected r-Regular Graphs}}}, doi = {{10.1137/22m1500654}}, volume = {{37}}, year = {{2023}}, } @article{33741, abstract = {{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.}}, author = {{Cappello, Chiara and Steffen, Eckhard}}, issn = {{0218-0006}}, journal = {{Annals of Combinatorics}}, keywords = {{Discrete Mathematics and Combinatorics}}, publisher = {{Springer Science and Business Media LLC}}, title = {{{Symmetric Set Coloring of Signed Graphs}}}, doi = {{10.1007/s00026-022-00593-4}}, year = {{2022}}, } @article{31543, author = {{Steffen, Eckhard and Wolf, Isaak Hieronymus}}, issn = {{0911-0119}}, journal = {{Graphs and Combinatorics}}, keywords = {{Discrete Mathematics and Combinatorics, Theoretical Computer Science}}, number = {{3}}, publisher = {{Springer Science and Business Media LLC}}, title = {{{Even Factors in Edge-Chromatic-Critical Graphs with a Small Number of Divalent Vertices}}}, doi = {{10.1007/s00373-022-02506-x}}, volume = {{38}}, year = {{2022}}, } @article{33950, author = {{Cappello, Chiara and Steffen, Eckhard}}, issn = {{0166-218X}}, journal = {{Discrete Applied Mathematics}}, keywords = {{Applied Mathematics, Discrete Mathematics and Combinatorics}}, pages = {{183--193}}, publisher = {{Elsevier BV}}, title = {{{Frustration-critical signed graphs}}}, doi = {{10.1016/j.dam.2022.08.010}}, volume = {{322}}, year = {{2022}}, } @article{26408, author = {{Mattiolo, Davide and Steffen, Eckhard}}, issn = {{0364-9024}}, journal = {{Journal of Graph Theory}}, number = {{3}}, pages = {{399--413}}, title = {{{Edge colorings and circular flows on regular graphs}}}, doi = {{10.1002/jgt.22746}}, volume = {{99}}, year = {{2022}}, } @inproceedings{22287, author = {{Gräßler, Iris and Roesmann, Daniel and Cappello, Chiara and Steffen, Eckhard}}, booktitle = {{Procedia CIRP Design}}, editor = {{Lutters, Eric}}, issn = {{2212-8271}}, location = {{Enschede}}, pages = {{433--438}}, publisher = {{Elsevier}}, title = {{{Skill-based worker assignment in a manual assembly line}}}, doi = {{10.1016/j.procir.2021.05.100}}, year = {{2021}}, } @article{34042, author = {{Li, Jiaao and Ma, Yulai and Miao, Zhengke and Shi, Yongtang and Wang, Weifan and Zhang, Cun-Quan}}, issn = {{0095-8956}}, journal = {{Journal of Combinatorial Theory, Series B}}, keywords = {{Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Theoretical Computer Science}}, pages = {{61--80}}, publisher = {{Elsevier BV}}, title = {{{Nowhere-zero 3-flows in toroidal graphs}}}, doi = {{10.1016/j.jctb.2021.11.001}}, volume = {{153}}, year = {{2021}}, }