A family of multigraphs with large palette index
| Autor: | Maddalena Avesani, Arrigo Bonisoli, Giuseppe Mazzuoccolo |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
Palette index
edge-coloring interval edge-coloring Algebra and Number Theory Mathematics::Combinatorics Statistics::Applications Multigraph Quadratic function Computer Science::Social and Information Networks Theoretical Computer Science Vertex (geometry) Combinatorics Edge coloring 05C15 Computer Science::Discrete Mathematics Computer Science::Multimedia FOS: Mathematics Discrete Mathematics and Combinatorics Mathematics - Combinatorics Edge-coloring Interval edge-coloring Geometry and Topology Combinatorics (math.CO) Mathematics |
| Zdroj: | Ars mathematica contemporanea |
| Popis: | Given a proper edge-coloring of a loopless multigraph, the palette of a vertex is defined as the set of colors of the edges which are incident with it. The palette index of a multigraph is defined as the minimum number of distinct palettes occurring among the vertices, taken over all proper edge-colorings of the multigraph itself. In this framework, the palette multigraph of an edge-colored multigraph is defined in this paper and some of its properties are investigated. We show that these properties can be applied in a natural way in order to produce the first known family of multigraphs whose palette index is expressed in terms of the maximum degree by a quadratic polynomial. We also attempt an analysis of our result in connection with some related questions. 13 pages, 2 figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|