On minimal triangle-free graphs with prescribed k-defective chromatic number
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)...
| Main Authors: | , , |
|---|---|
| Format: | Journal Article |
| Published: |
Elsevier Science BV
2011
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/20.500.11937/24432 |
| _version_ | 1848751427720052736 |
|---|---|
| author | Achuthan, Nirmala Achuthan, Narasimaha Simanihuruk, M. |
| author_facet | Achuthan, Nirmala Achuthan, Narasimaha Simanihuruk, M. |
| author_sort | Achuthan, Nirmala |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | 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). |
| first_indexed | 2025-11-14T07:52:33Z |
| format | Journal Article |
| id | curtin-20.500.11937-24432 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T07:52:33Z |
| publishDate | 2011 |
| publisher | Elsevier Science BV |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-244322017-09-13T15:52:51Z On minimal triangle-free graphs with prescribed k-defective chromatic number Achuthan, Nirmala Achuthan, Narasimaha Simanihuruk, M. k-defective chromatic number Triangle-free graphs k-independence 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). 2011 Journal Article http://hdl.handle.net/20.500.11937/24432 10.1016/j.disc.2010.08.013 Elsevier Science BV unknown |
| spellingShingle | k-defective chromatic number Triangle-free graphs k-independence Achuthan, Nirmala Achuthan, Narasimaha Simanihuruk, M. On minimal triangle-free graphs with prescribed k-defective chromatic number |
| title | On minimal triangle-free graphs with prescribed k-defective chromatic number |
| title_full | On minimal triangle-free graphs with prescribed k-defective chromatic number |
| title_fullStr | On minimal triangle-free graphs with prescribed k-defective chromatic number |
| title_full_unstemmed | On minimal triangle-free graphs with prescribed k-defective chromatic number |
| title_short | On minimal triangle-free graphs with prescribed k-defective chromatic number |
| title_sort | on minimal triangle-free graphs with prescribed k-defective chromatic number |
| topic | k-defective chromatic number Triangle-free graphs k-independence |
| url | http://hdl.handle.net/20.500.11937/24432 |