2015/01/19 by Nirmala Achuthan, Achuthan, Nirmala, N. R. Achuthan +3
Mathematics · #05C15 #05C35 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C15 #msc:05C35
paper · pdf · doi:10.48550/arxiv.1501.04384
17pages, 5figures
arxiv created 2015/01/19 · arxiv updated 2015/01/20
A graph is (m, k)-colourable if its vertices can be coloured with m colours such that the maximum degree of any subgraph induced on ver- tices receiving the same colour is at most k. The k-defective chromatic number for a graph is the least positive integer m for which the graph is (m, k)-colourable. All triangle-free graphs on 8 or fewer vertices are (2, 1)-colourable. There are exactly four triangle-free graphs of order 9 which have 1-defective chromatic number 3. We show that these four graphs appear as subgraphs in almost all triangle-free graphs of order 10 with 1-defective chromatic number equal to 3. In fact there is a unique triangle-free (3, 1)-critical graph on 10 vertices and we exhibit this graph.