Hoffman colorings of graphs
| Autor: | Abiad, Aida, Bosma, Wieb, van Veluw, Thijs |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | Hoffman's bound is a well-known spectral bound on the chromatic number of a graph, known to be tight for instance for bipartite graphs. While Hoffman colorings (colorings attaining the bound) were studied before for regular graphs, for irregular graphs not much is known. We investigate tightness of the Hoffman bound, with a particular focus on irregular graphs, obtaining several results on the graph structure of Hoffman colorings. In particular, we study the connection between Hoffman colorability and graph tensor products, and as a byproduct, we obtain constructions of infinite families of irregular Hoffman colorable graphs. Moreover, we present a Decomposition Theorem, which describes the structure of Hoffman colorings, and we use it to completely classify Hoffman colorability of cone graphs and line graphs. We also prove a partial converse, the Composition Theorem, leading to various new constructions of Hoffman colorable graphs and to an algorithm for computing all connected Hoffman colorable graphs for some given number of vertices and colors. Since several graph coloring parameters are known to be sandwiched between the Hoffman bound and the chromatic number, as a byproduct of our results on Hoffman colorability, we obtain the values of such chromatic parameters. Comment: v1: Master Thesis in Mathematics of the third author, supervised by first two authors v2: Article, consisting of parts of the thesis (v1) |
| Databáze: | arXiv |
| Externí odkaz: |
|