Chordal signed graphs and signed bigraphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909984142393344 |
|---|---|
| author | Huang, Jing Ye, Ying Ying |
| author_facet | Huang, Jing Ye, Ying Ying |
| contents | Chordal graphs and chordal bigraphs enjoy beautiful characterizations, in terms of forbidden subgraphs, vertex/edge orderings, vertex/edge separating sets, and tree-like representations. In this paper, we introduce chordal signed graphs and chordal signed bigraphs. Interestingly, chordal signed graphs are equivalent to strict chordal digraphs studied by Hell and Hernández-Cruz. A forbidden subdigraph characterization of strict chordal digraphs can be translated to a forbidden subgraph characterization of chordal signed graphs. We give a forbidden subgraph characterization of chordal signed bigraphs. The forbidden subgraphs for chordal signed bigraphs are analogous to those for chordal signed graphs but the proofs are much more complicated and intriguing. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_14886 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Chordal signed graphs and signed bigraphs Huang, Jing Ye, Ying Ying Combinatorics Chordal graphs and chordal bigraphs enjoy beautiful characterizations, in terms of forbidden subgraphs, vertex/edge orderings, vertex/edge separating sets, and tree-like representations. In this paper, we introduce chordal signed graphs and chordal signed bigraphs. Interestingly, chordal signed graphs are equivalent to strict chordal digraphs studied by Hell and Hernández-Cruz. A forbidden subdigraph characterization of strict chordal digraphs can be translated to a forbidden subgraph characterization of chordal signed graphs. We give a forbidden subgraph characterization of chordal signed bigraphs. The forbidden subgraphs for chordal signed bigraphs are analogous to those for chordal signed graphs but the proofs are much more complicated and intriguing. |
| title | Chordal signed graphs and signed bigraphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2512.14886 |