A Neighborhood Condition Which Implies the Existence of a Class of D‐chromatic Subgraphs
Document Type
Article
Publication Date
1-1-1994
Description
A graph G of order n satisfies the neighborhood condition NCk > s if any collection of k independent vertices is collectively adjacent to more than s vertices. Given a family H of graphs, the decomposition class β(H) is the family of graphs B with the property that for some H ∈ H of chromatic number d, H contains B as an induced subgraph and l̀V(H) − V(B)ǹ is (d − 2) colorable. Let H be a family of d‐chromatic graphs, B an element of β(H) such that B contains an s‐matching as an induced subgraph. Thus the cardinality of one of the partite sets of B is s + r for some integer r ≥ 0. We show that if t is a fixed positive integer, G is a graph of sufficiently large order n that satisfies the neighborhood condition (Formula Presented.) then G contains B + K(d ‐ 2; t) as a subgraph.
Citation Information
Knisley, Debra J.. 1994. A Neighborhood Condition Which Implies the Existence of a Class of D‐chromatic Subgraphs. Journal of Graph Theory. Vol.18(1). 59-71. https://doi.org/10.1002/jgt.3190180107 ISSN: 0364-9024