The Nordhaus-Gaddum problem for the k-defective chromatic number of a P4-free graph
A graph is (m, k)-colourable if its vertices can be coloured with m colours such that the maximum degree of the subgraph induced on vertices receiving the same colour is at most k. The k-defective chromatic number Xk(G) of a graph G is the least positive integer m for which G is (m, k)-colourable. T...
| Main Authors: | , , |
|---|---|
| Format: | Journal Article |
| Published: |
Centre for Discrete Mathematics and Computing
2011
|
| Online Access: | http://hdl.handle.net/20.500.11937/11944 |
| _version_ | 1848747940396400640 |
|---|---|
| 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 is (m, k)-colourable if its vertices can be coloured with m colours such that the maximum degree of the subgraph induced on vertices receiving the same colour is at most k. The k-defective chromatic number Xk(G) of a graph G is the least positive integer m for which G is (m, k)-colourable. The Nordhaus-Gaddum problem is to find sharp bounds for Xk(G)+Xk(G) and Xk(G). Xk(G) over the set of all graphs of order p where G is the complement of the graph G. In this paper we obtain a sharp upper bound for Xk(G)+Xk(G), where G is a P4-free graph of order p and k = 1 or 2. |
| first_indexed | 2025-11-14T06:57:08Z |
| format | Journal Article |
| id | curtin-20.500.11937-11944 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T06:57:08Z |
| publishDate | 2011 |
| publisher | Centre for Discrete Mathematics and Computing |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-119442017-03-08T13:12:21Z The Nordhaus-Gaddum problem for the k-defective chromatic number of a P4-free graph Achuthan, Nirmala Achuthan, Narasimaha Simanihuruk, M. A graph is (m, k)-colourable if its vertices can be coloured with m colours such that the maximum degree of the subgraph induced on vertices receiving the same colour is at most k. The k-defective chromatic number Xk(G) of a graph G is the least positive integer m for which G is (m, k)-colourable. The Nordhaus-Gaddum problem is to find sharp bounds for Xk(G)+Xk(G) and Xk(G). Xk(G) over the set of all graphs of order p where G is the complement of the graph G. In this paper we obtain a sharp upper bound for Xk(G)+Xk(G), where G is a P4-free graph of order p and k = 1 or 2. 2011 Journal Article http://hdl.handle.net/20.500.11937/11944 Centre for Discrete Mathematics and Computing restricted |
| spellingShingle | Achuthan, Nirmala Achuthan, Narasimaha Simanihuruk, M. The Nordhaus-Gaddum problem for the k-defective chromatic number of a P4-free graph |
| title | The Nordhaus-Gaddum problem for the k-defective chromatic number of a P4-free graph |
| title_full | The Nordhaus-Gaddum problem for the k-defective chromatic number of a P4-free graph |
| title_fullStr | The Nordhaus-Gaddum problem for the k-defective chromatic number of a P4-free graph |
| title_full_unstemmed | The Nordhaus-Gaddum problem for the k-defective chromatic number of a P4-free graph |
| title_short | The Nordhaus-Gaddum problem for the k-defective chromatic number of a P4-free graph |
| title_sort | nordhaus-gaddum problem for the k-defective chromatic number of a p4-free graph |
| url | http://hdl.handle.net/20.500.11937/11944 |