Extension of the Gyárfás-Sumner conjecture to signed graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917061657100288 |
|---|---|
| author | Aubian, Guillaume Ibiapina, Allen Kuffner, Luis Naserasr, Reza Pujol, Cyril Robin, Cléophée Zhou, Huan |
| author_facet | Aubian, Guillaume Ibiapina, Allen Kuffner, Luis Naserasr, Reza Pujol, Cyril Robin, Cléophée Zhou, Huan |
| contents | The balanced chromatic number of a signed graph G is the minimum number of balanced sets that cover all vertices of G. Studying structural conditions which imply bounds on the balanced chromatic number of signed graphs is among the most fundamental problems in graph theory. In this work, we initiate the study of coloring hereditary classes of signed graphs. More precisely, we say that a set F = {F_1, F_2, ..., F_l} is a GS (for Gyárfás-Sumner) set if there exists a constant c such that signed graphs with no induced subgraph switching equivalent to a member of F admit a balanced c-coloring. The focus of this work is to study GS sets of order 2. We show that if F is a GS set of order 2, then F_1 is either (K_3, -) or (K_4, -), and F_2 is a linear forest. In the case of F_1 = (K_3, -), we show that any choice of a linear forest for F_2 works. In the case of F_1 = (K_4, -), we show that if each connected component of F_2 is a path of length at most 4, then {F_1, F_2} is a GS set. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_03335 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Extension of the Gyárfás-Sumner conjecture to signed graphs Aubian, Guillaume Ibiapina, Allen Kuffner, Luis Naserasr, Reza Pujol, Cyril Robin, Cléophée Zhou, Huan Combinatorics Discrete Mathematics The balanced chromatic number of a signed graph G is the minimum number of balanced sets that cover all vertices of G. Studying structural conditions which imply bounds on the balanced chromatic number of signed graphs is among the most fundamental problems in graph theory. In this work, we initiate the study of coloring hereditary classes of signed graphs. More precisely, we say that a set F = {F_1, F_2, ..., F_l} is a GS (for Gyárfás-Sumner) set if there exists a constant c such that signed graphs with no induced subgraph switching equivalent to a member of F admit a balanced c-coloring. The focus of this work is to study GS sets of order 2. We show that if F is a GS set of order 2, then F_1 is either (K_3, -) or (K_4, -), and F_2 is a linear forest. In the case of F_1 = (K_3, -), we show that any choice of a linear forest for F_2 works. In the case of F_1 = (K_4, -), we show that if each connected component of F_2 is a path of length at most 4, then {F_1, F_2} is a GS set. |
| title | Extension of the Gyárfás-Sumner conjecture to signed graphs |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2511.03335 |