Name
Title | ||
|---|---|---|
On bounding the difference between the maximum degree and the chromatic number by a constant |
Abstract | ||
|---|---|---|
For every $k \in \mathbb{N}_0$, we consider graphs $G$ where for every induced subgraph $H$ of $G$, $\Delta(H) \leq \chi(H) -1 + k$ holds, where $\Delta(H)$ is the maximum degree and $\chi(H)$ is the chromatic number of the subgraph $H$. Let us call this family of graphs~$\varUpsilon_k$. We give a finite forbidden induced subgraph characterization of $\varUpsilon_k$ for every $k$. We compare these results with those given in On bounding the difference between the maximum degree and the clique number, Graphs and Combinatorics 31(5): 1689-1702 (2015), where we studied the graphs in which for any induced subgraph $H$, $\Delta(H) \leq \omega(H) -1 + k$ holds, where $\omega(H)$ denotes the clique number of a graph. In particular, we introduce the class of neighborhood perfect graphs, that is, those graphs where the neighborhood of every vertex is perfect. We find a nice characterization of this graph class in terms of $\varOmega_k$ and $\varUpsilon_k$: We prove that a graph $G$ is a neighborhood perfect graph if and only if for every induced subgraph $H$ of $G$, $H \in \varUpsilon_k$ if and only if $H \in \varOmega_k$ for all $k \in \mathbb{N}_0$. |
Year | Venue | DocType |
|---|---|---|
2015 | CoRR | Journal |
Volume | Citations | PageRank |
abs/1511.08403 | 0 | 0.34 |
References | Authors | |
1 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Oliver Schaudt | 1 | 95 | 21.74 |
| vera weil | 2 | 0 | 0.34 |