Improvement on Brooks' chromatic bound for a class of graphs |
| |
Authors: | Medha Dhurandhar |
| |
Affiliation: | Indian Institute of Science, Bangalore, India |
| |
Abstract: | Brooks' Theorem says that if for a graph G,Δ(G)=n, then G is n-colourable, unless (1) n=2 and G has an odd cycle as a component, or (2) n>2 and Kn+1 is a component of G. In this paper we prove that if a graph G has none of some three graphs (K1,3;K5?e and H) as an induced subgraph and if Δ(G)?6 and d(G)<Δ(G), then χ(G)<Δ(G). Also we give examples to show that the hypothesis Δ(G)?6 can not be non-trivially relaxed and the graph K5?e can not be removed from the hypothesis. Moreover, for a graph G with none of K1,3;K5?e and H as an induced subgraph, we verify Borodin and Kostochka's conjecture that if for a graph G,Δ(G)?9 and d(G)<Δ(G), then χ(G)<Δ(G). |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|