Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2508.11008 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913992129118208 |
|---|---|
| author | Granada, Fabricio Mendoza Manlove, David |
| author_facet | Granada, Fabricio Mendoza Manlove, David |
| contents | A b-chromatic colouring of a graph $G$ is a proper $k$-colouring of the vertices of $G$, for some integer $k$, such that, for each colour $i$ ($1\leq i\leq k$), there exists a vertex $v$ of colour $i$ such that $v$ is adjacent to a vertex of colour $j$, for each $j$ ($1\leq j\leq k$, $j\neq i$). The b-chromatic number of $G$ is the maximum integer $k$ such that $G$ admits a b-chromatic colouring using $k$ colours. In this paper we introduce the concept of a total b-chromatic colouring, which extends the notion of b-chromatic colourings to both vertices and edges in a graph. We show that the problem of computing the total b-chromatic number is NP-hard in general graphs. On the other hand for a subclass of caterpillars we give a polynomial-time algorithm to compute the total b-chromatic number, and indeed a total b-chromatic colouring with the maximum number of colours. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_11008 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Total b-chromatic Colouring of Graphs Granada, Fabricio Mendoza Manlove, David Combinatorics F.2.2 A b-chromatic colouring of a graph $G$ is a proper $k$-colouring of the vertices of $G$, for some integer $k$, such that, for each colour $i$ ($1\leq i\leq k$), there exists a vertex $v$ of colour $i$ such that $v$ is adjacent to a vertex of colour $j$, for each $j$ ($1\leq j\leq k$, $j\neq i$). The b-chromatic number of $G$ is the maximum integer $k$ such that $G$ admits a b-chromatic colouring using $k$ colours. In this paper we introduce the concept of a total b-chromatic colouring, which extends the notion of b-chromatic colourings to both vertices and edges in a graph. We show that the problem of computing the total b-chromatic number is NP-hard in general graphs. On the other hand for a subclass of caterpillars we give a polynomial-time algorithm to compute the total b-chromatic number, and indeed a total b-chromatic colouring with the maximum number of colours. |
| title | Total b-chromatic Colouring of Graphs |
| topic | Combinatorics F.2.2 |
| url | https://arxiv.org/abs/2508.11008 |