Graph polynomials: some questions on the edge
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916297558720512 |
|---|---|
| author | Farr, Graham Morgan, Kerri |
| author_facet | Farr, Graham Morgan, Kerri |
| contents | We raise some questions about graph polynomials, highlighting concepts and phenomena that may merit consideration in the development of a general theory. Our questions are mainly of three types: When do graph polynomials have reduction relations (simple linear recursions based on local operations), perhaps in a wider class of combinatorial objects? How many levels of reduction relations does a graph polynomial need in order to express it in terms of trivial base cases? For a graph polynomial, how are properties such as equivalence and factorisation reflected in the structure of a graph? We illustrate our discussion with a variety of graph polynomials and other invariants. This leads us to reflect on the historical origins of graph polynomials. We also introduce some new polynomials based on partial colourings of graphs and establish some of their basic properties. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_15746 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Graph polynomials: some questions on the edge Farr, Graham Morgan, Kerri Combinatorics Computational Complexity Discrete Mathematics 05C31, 05C15, 68Q17 G.2.2; F.2.2 We raise some questions about graph polynomials, highlighting concepts and phenomena that may merit consideration in the development of a general theory. Our questions are mainly of three types: When do graph polynomials have reduction relations (simple linear recursions based on local operations), perhaps in a wider class of combinatorial objects? How many levels of reduction relations does a graph polynomial need in order to express it in terms of trivial base cases? For a graph polynomial, how are properties such as equivalence and factorisation reflected in the structure of a graph? We illustrate our discussion with a variety of graph polynomials and other invariants. This leads us to reflect on the historical origins of graph polynomials. We also introduce some new polynomials based on partial colourings of graphs and establish some of their basic properties. |
| title | Graph polynomials: some questions on the edge |
| topic | Combinatorics Computational Complexity Discrete Mathematics 05C31, 05C15, 68Q17 G.2.2; F.2.2 |
| url | https://arxiv.org/abs/2406.15746 |