Journal article icon

Journal article

On the divisibility of graphs

Abstract:

A graph G is k-divisible if for each induced subgraph H of G with at least one edge, there is a partition of the vertex set of H into sets V1,..., Vk such that no Vi contains a maximum clique of H. We show that a claw-free graph is 2-divisible if and only if it does not contain an odd hole: we conjecture that this result is true for any graph, and present further conjectures relating 2-divisibility to the strong perfect graph conjecture. We also present related results involving the chromatic...

Expand abstract
Publication status:
Published

Actions


Access Document


Authors


Journal:
DISCRETE MATHEMATICS
Volume:
242
Issue:
1-3
Pages:
145-156
Publication date:
2002-01-06
DOI:
ISSN:
0012-365X
URN:
uuid:dd3ea4e4-85ee-446e-8495-d93e7e152a4d
Source identifiers:
102306
Local pid:
pubs:102306
Language:
English
Keywords:

Terms of use


Metrics


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP