On minimal triangle-free graphs with prescribed k-defective chromatic number

Abstract

A graph G is (m, k)-colourable if its vertices can be coloured with m colours such that the maximum degree of any subgraph induced on vertices receiving the same colour is at most k. The k-defective chromatic number χk(G) is the least positive integer m for which G is (m, k)-colourable. Let f(m, k) be the smallest order of a triangle-free graph such that χk(G)=m. In this paper we study the problem of determining f(m, k). We show that f(3, 2)=13 and characterize the corresponding minimal graphs. We present a lower bound for f(m, k) for all m≥3 and also an upper bound for f(3, k).