Name
Title | ||
|---|---|---|
On bounding the difference between the maximum degree and the chromatic number by a constant. |
Abstract | ||
|---|---|---|
We provide a finite forbidden induced subgraph characterization for the graph class Υk, for all k∈N0, which is defined as follows. A graph is in Υk if for any induced subgraph, Δ≤χ−1+k holds, where Δ is the maximum degree and χ is the chromatic number of the subgraph. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.dam.2016.11.018 | Discrete Applied Mathematics |
Keywords | Field | DocType |
Maximum degree,Graph coloring,Chromatic number,Structural characterization of families of graphs,Hereditary graph class,Neighborhood perfect graphs | Perfect graph,Discrete mathematics,Combinatorics,Claw-free graph,Induced subgraph isomorphism problem,Induced subgraph,Distance-hereditary graph,Degree (graph theory),Factor-critical graph,Universal graph,Mathematics | Journal |
Volume | Issue | ISSN |
231 | C | 0166-218X |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vera Weil | 1 | 1 | 2.65 |
| Oliver Schaudt | 2 | 95 | 21.74 |