The NordhausGaddum problem for the kdefective chromatic number of a P4free graph
Abstract
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 kdefective chromatic number Xk(G) of a graph G is the least positive integer m for which G is (m, k)colourable. The NordhausGaddum 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 P4free graph of order p and k = 1 or 2.
Citation
Achuthan, Nirmala and Achuthan, N.R. and Simanihuruk, M. 2011. The NordhausGaddum problem for the kdefective chromatic number of a P4free graph. The Australasian Journal of Combinatorics. 49: pp. 313.
Source Title
The Australasian Journal of Combinatorics
ISSN
School
Department of Mathematics and Statistics
Collection
Related items
Showing items related by title, author, creator and subject.

Achuthan, Nirmala; Achuthan, Narasimaha; Simanihuruk, M. (2011)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 kdefective chromatic number χk(G) ...

Ananchuen, Nawarat (1994)Let G be a simple connected graph on 2n vertices with a perfect matching. For 1 ≤ k ≤ n  1, G is said to be kextendable if for every matching M of size k in G there is a perfect matching in G containing all the edges ...

Ananchuen, Watcharaphong (1993)A graph G is said to have property P(m,n,k) if for any set of m + n distinct vertices there are at least k other vertices, each of which is adjacent to the first m vertices but not adjacent to any of the latter n vertices. ...