Some Defective Parameters in Graphs
Graphs and Combinatorics, cilt.29, sa.2, ss.213-224, 2013 (SCI-Expanded, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 29 Sayı: 2
- Basım Tarihi: 2013
- Doi Numarası: 10.1007/s00373-011-1111-5
- Dergi Adı: Graphs and Combinatorics
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
- Sayfa Sayıları: ss.213-224
- Anahtar Kelimeler: Cocoloring, Coloring, Defective cocoloring, Defective coloring
- Boğaziçi Üniversitesi Adresli: Evet
Özet
Given a graph G and an integer k, a set S of vertices in G is k-sparse if S induces a graph with a maximum degree of at most k. Many parameters in graph theory are defined in terms of independent sets. Accordingly, their definitions can be expanded taking into account the notion of k-sparse sets. In this discussion, we examine several of those extensions. Similarly, S is k-dense if S induces a k-sparse graph in the complement of G. A partition of V(G) is a k-defective cocoloring if each part is k-sparse or k-dense. The minimum order of all k-defective cocolorings is the k-defective cochromatic number of G and denoted zk (G). Analogous notions are defined similarly for k-defective coloring where V(G) is partitioned into k-sparse parts. We show the NP-hardness of computing maximum k-defective sets in planar graphs with maximum degree at most k + 1 and arbitrarily large girth. We explore the extension of Ramsey numbers to k-sparse and k-dense sets of vertices. Lastly, we discuss some bounds related to k-defective colorings and k-defective cocolorings. © 2011 Springer.