Linear Chromatic Bounds for a Subfamily of 3K 1-free Graphs |
| |
| Authors: | S. A. Choudum T. Karthick M. A. Shalu |
| |
| Affiliation: | (1) Department of Mathematics, Indian Institute of Technology Madras, Chennai, 600 036, India;(2) Department of Mathematics, Birla Institute of Technology and Science, Pilani, Goa campus, Goa, 403 726, India |
| |
| Abstract: | For an arbitrary class of graphs  , there may not exist a function f such that  , for every  . When such a function exists, it is called a χ-binding function for  . The problem of finding an optimal χ-binding function for the class of 3K 1-free graphs is open. In this paper, we obtain linear χ-binding function for the class of {3K 1, H}-free graphs, where H is one of the following graphs:  , House graph and Kite graph. We first describe structures of these graphs and then derive χ-binding functions. |
| |
| Keywords: | Graphs Chromatic number Clique number χ -binding function |
| 本文献已被 SpringerLink 等数据库收录！ |
|
