On minimal triangle-free graphs with prescribed k-defective chromatic number
| dc.contributor.author | Achuthan, Nirmala | |
| dc.contributor.author | Achuthan, Narasimaha | |
| dc.contributor.author | Simanihuruk, M. | |
| dc.date.accessioned | 2017-01-30T12:42:51Z | |
| dc.date.available | 2017-01-30T12:42:51Z | |
| dc.date.created | 2012-02-15T20:00:47Z | |
| dc.date.issued | 2011 | |
| dc.identifier.citation | Achuthan, Nirmala and Achuthan, N.R. and Simanihuruk, M. 2011. On minimal triangle-free graphs with prescribed k-defective chromatic number. Discrete Mathematics. 311 (13): pp. 1119-1127. | |
| dc.identifier.uri | http://hdl.handle.net/20.500.11937/24432 | |
| dc.identifier.doi | 10.1016/j.disc.2010.08.013 | |
| dc.description.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). | |
| dc.publisher | Elsevier Science BV | |
| dc.subject | k-defective chromatic number | |
| dc.subject | Triangle-free graphs | |
| dc.subject | k-independence | |
| dc.title | On minimal triangle-free graphs with prescribed k-defective chromatic number | |
| dc.type | Journal Article | |
| dcterms.source.volume | 311 | |
| dcterms.source.number | 13 | |
| dcterms.source.startPage | 1119 | |
| dcterms.source.endPage | 1127 | |
| dcterms.source.issn | 0012365X | |
| dcterms.source.title | Discrete Mathematics | |
| curtin.department | Department of Mathematics and Statistics | |
| curtin.accessStatus | Open access via publisher |