The NordhausGaddum problem for the kdefective chromatic number of a P4free graph
Access Status
Fulltext not available
Authors
Achuthan, Nirmala
Achuthan, Narasimaha
Simanihuruk, M.
Date
2011Type
Journal Article
Metadata
Show full item recordCitation
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
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.
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. ...