Affordable Access

On triangle-free graphs of order 10 with prescribed 1-defective chromatic number

Authors
  • Achuthan, Nirmala
  • Achuthan, N. R.
  • Keady, G.
Type
Preprint
Publication Date
Jan 18, 2015
Submission Date
Jan 18, 2015
Identifiers
arXiv ID: 1501.04384
Source
arXiv
License
Yellow
External links

Abstract

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.

Report this publication

Statistics

Seen <100 times