Affordable Access

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

Authors
Type
Preprint
Publication Date
Submission Date
Identifiers
arXiv ID: 1501.04384
Source
arXiv
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.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments