Some Defective Parameters in Graphs |
| |
Authors: | T Ekim J Gimbel |
| |
Institution: | 1. Department of Industrial Engineering, Bogazici University, Bebek, 34342, Istanbul, Turkey 2. Mathematics and Statistics, University of Alaska, Fairbanks, AK, 99775-6660, USA
|
| |
Abstract: | 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 z k (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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|