An Open Problem on k-Defective Colourings of Triangle-free Graphs and their Complements
Mudin Simanihuruk · 2010
A graph G is (m,k)-colourable if its vertices can be coloured with m colours such that the maximum degree of the subgraph induced on ver-tices 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. Maddox proved that χk(G)+χk(Ḡ) ≤ 5 p3k+4 whenever G is a triangle-free of order p and k ≥ 0 is an integer. Simanihuruk et al proved that Maddox’s upper bound is a weak upper bound for k = 1. In this paper a better upper bound of χk(G) + χk(Ḡ) is established whenever G is a triangle-free graph and k = 2. Hence finding a sharp upper bound of χk(G) + χk(Ḡ) is an open problem whenever G is a triangle-free graph.