---
_id: '33741'
abstract:
- lang: eng
  text: 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:
- first_name: Chiara
  full_name: Cappello, Chiara
  id: '72874'
  last_name: Cappello
- first_name: Eckhard
  full_name: Steffen, Eckhard
  id: '15548'
  last_name: Steffen
  orcid: 0000-0002-9808-7401
citation:
  ama: Cappello C, Steffen E. Symmetric Set Coloring of Signed Graphs. <i>Annals of
    Combinatorics</i>. Published online 2022. doi:<a href="https://doi.org/10.1007/s00026-022-00593-4">10.1007/s00026-022-00593-4</a>
  apa: Cappello, C., &#38; Steffen, E. (2022). Symmetric Set Coloring of Signed Graphs.
    <i>Annals of Combinatorics</i>. <a href="https://doi.org/10.1007/s00026-022-00593-4">https://doi.org/10.1007/s00026-022-00593-4</a>
  bibtex: '@article{Cappello_Steffen_2022, title={Symmetric Set Coloring of Signed
    Graphs}, DOI={<a href="https://doi.org/10.1007/s00026-022-00593-4">10.1007/s00026-022-00593-4</a>},
    journal={Annals of Combinatorics}, publisher={Springer Science and Business Media
    LLC}, author={Cappello, Chiara and Steffen, Eckhard}, year={2022} }'
  chicago: Cappello, Chiara, and Eckhard Steffen. “Symmetric Set Coloring of Signed
    Graphs.” <i>Annals of Combinatorics</i>, 2022. <a href="https://doi.org/10.1007/s00026-022-00593-4">https://doi.org/10.1007/s00026-022-00593-4</a>.
  ieee: 'C. Cappello and E. Steffen, “Symmetric Set Coloring of Signed Graphs,” <i>Annals
    of Combinatorics</i>, 2022, doi: <a href="https://doi.org/10.1007/s00026-022-00593-4">10.1007/s00026-022-00593-4</a>.'
  mla: Cappello, Chiara, and Eckhard Steffen. “Symmetric Set Coloring of Signed Graphs.”
    <i>Annals of Combinatorics</i>, Springer Science and Business Media LLC, 2022,
    doi:<a href="https://doi.org/10.1007/s00026-022-00593-4">10.1007/s00026-022-00593-4</a>.
  short: C. Cappello, E. Steffen, Annals of Combinatorics (2022).
date_created: 2022-10-17T07:54:41Z
date_updated: 2023-05-16T10:37:58Z
department:
- _id: '542'
doi: 10.1007/s00026-022-00593-4
external_id:
  arxiv:
  - '2106.05928'
keyword:
- Discrete Mathematics and Combinatorics
language:
- iso: eng
publication: Annals of Combinatorics
publication_identifier:
  issn:
  - 0218-0006
  - 0219-3094
publication_status: published
publisher: Springer Science and Business Media LLC
status: public
title: Symmetric Set Coloring of Signed Graphs
type: journal_article
user_id: '15540'
year: '2022'
...