Journal article
Induced subgraphs of graphs with large chromatic number. XII. Distant stars
- Abstract:
- The Gy´arf´as-Sumner conjecture asserts that if H is a tree then every graph with bounded clique number and very large chromatic number contains H as an induced subgraph. This is still open, although it has been proved for a few simple families of trees, including trees of radius two, some special trees of radius three, and subdivided stars. These trees all have the property that their vertices of degree more than two are clustered quite closely together. In this paper, we prove the conjecture for two families of trees which do not have this restriction. As special cases, these families contain all double-ended brooms and two-legged caterpillars.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 302.9KB, Terms of use)
-
- Publisher copy:
- 10.1002/jgt.22450
Authors
- Publisher:
- Wiley
- Journal:
- Journal of Graph Theory More from this journal
- Volume:
- 92
- Issue:
- 3
- Pages:
- 237-254
- Publication date:
- 2019-02-11
- Acceptance date:
- 2018-12-19
- DOI:
- EISSN:
-
1097-0118
- ISSN:
-
0364-9024
- Pubs id:
-
pubs:953280
- UUID:
-
uuid:c2452827-3632-4a7e-8997-e237897166a7
- Local pid:
-
pubs:953280
- Source identifiers:
-
953280
- Deposit date:
-
2018-12-19
Terms of use
- Copyright holder:
- Wiley Periodicals, Inc
- Copyright date:
- 2019
- Rights statement:
- © 2019 Wiley Periodicals, Inc.
- Notes:
- This is the accepted manuscript version of the article. The final version is available online from Wiley at: 10.1002/jgt.22450
If you are the owner of this record, you can report an update to it here: Report update to this record