On minimal triangle-free graphs with prescribed k-defective chromatic number
Access Status
Open access via publisher
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. On minimal triangle-free graphs with prescribed k-defective chromatic number. Discrete Mathematics. 311 (13): pp. 1119-1127.
Source Title
Discrete Mathematics
ISSN
School
Department of Mathematics and Statistics
Collection
Abstract
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).
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 k-defective 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 k-extendable 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. ...