On minimal trianglefree graphs with prescribed kdefective chromatic number
Access Status
Open access via publisher
Date
2011Type
Journal Article
Metadata
Show full item recordAbstract
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) is the least positive integer m for which G is (m, k)colourable. Let f(m, k) be the smallest order of a trianglefree 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).
Citation
Achuthan, Nirmala and Achuthan, N.R. and Simanihuruk, M. 2011. On minimal trianglefree graphs with prescribed kdefective chromatic number. Discrete Mathematics. 311 (13): pp. 11191127.
Source Title
Discrete Mathematics
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 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) ...

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. ...