Name
Abstract | ||
|---|---|---|
For every $$k \\in {\\mathbb {N}}_0$$k¿N0, we consider graphs in which for any induced subgraph, $$\\Delta \\le \\omega - 1 + k$$Δ≤¿-1+k holds, where $$\\Delta $$Δ is the maximum degree and $$\\omega $$¿ is the maximum clique number of the subgraph. We give a finite forbidden induced subgraph characterization for every $$k$$k. As an application, we find some results on the chromatic number $$\\chi $$¿ of a graph. B. Reed stated the conjecture that for every graph, $$\\chi \\le \\lceil \\frac{\\Delta + \\omega + 1 }{2}\\rceil $$¿≤¿Δ+¿+12¿ holds. Since this inequality is fulfilled by graphs in which $$\\Delta \\le \\omega + 2$$Δ≤¿+2 holds, our results provide a hereditary graph class for which the conjecture holds. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/s00373-014-1468-3 | Graphs and Combinatorics |
Keywords | Field | DocType |
Maximum clique, Maximum degree, Structural characterization of families of graphs, Coloring of graphs | Discrete mathematics,Topology,Graph,Combinatorics,Clique number,Induced subgraph,Omega,Degree (graph theory),Conjecture,Mathematics,Bounding overwatch | Journal |
Volume | Issue | ISSN |
31 | 5 | 1435-5914 |
Citations | PageRank | References |
1 | 0.63 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Oliver Schaudt | 1 | 95 | 21.74 |
| Vera Weil | 2 | 1 | 2.65 |