@unpublished{44501, abstract = {{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. }}, author = {{Cappello, Chiara and Naserasr, Reza and Steffen, Eckhard and Wang, Zhouningxin}}, booktitle = {{arXiv:2304.10243}}, title = {{{Critically 3-frustrated signed graphs}}}, 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{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{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}}, } @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}}, }