{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T13:37:56Z","timestamp":1774359476521,"version":"3.50.1"},"reference-count":18,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2021,1,19]],"date-time":"2021-01-19T00:00:00Z","timestamp":1611014400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11801284"],"award-info":[{"award-number":["11801284"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Journal of Graph Theory"],"published-print":{"date-parts":[[2021,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Given two graphs  and , a graph is \u2010free if it contains no induced subgraph isomorphic to  or . For a positive integer ,  is the chordless path on  vertices. A <jats:italic>paraglider<\/jats:italic> is the graph that consists of a chorless cycle  plus a vertex adjacent to three vertices of the . In this paper, we study the structure of (, paraglider)\u2010free graphs, and show that every such graph  satisfies , where  and  are the chromatic number and clique number of , respectively. Our bound is attained by the complement of the Clebsch graph on 16 vertices. More strongly, we completely characterize all the (, paraglider)\u2010free graphs  that satisfies . We also construct an infinite family of (, paraglider)\u2010free graphs such that every graph  in the family has . This shows that our upper bound is optimal up to an additive constant and that there is no \u2010approximation algorithm for the chromatic number of (, paraglider)\u2010free graphs for any .<\/jats:p>","DOI":"10.1002\/jgt.22656","type":"journal-article","created":{"date-parts":[[2021,1,19]],"date-time":"2021-01-19T13:12:31Z","timestamp":1611061951000},"page":"305-323","update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["On graphs with no induced five\u2010vertex path or paraglider"],"prefix":"10.1002","volume":"97","author":[{"given":"Shenwei","family":"Huang","sequence":"first","affiliation":[{"name":"College of Computer Science Nankai University  Tianjin China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5950-9093","authenticated-orcid":false,"given":"T.","family":"Karthick","sequence":"additional","affiliation":[{"name":"Computer Science Unit Indian Statistical Institute, Chennai Centre Chennai India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2021,1,19]]},"reference":[{"key":"e_1_2_7_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.09.031"},{"key":"e_1_2_7_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2018.09.030"},{"key":"e_1_2_7_4_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20212"},{"key":"e_1_2_7_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-008-0801-0"},{"key":"e_1_2_7_6_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21730"},{"key":"e_1_2_7_7_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22572"},{"key":"e_1_2_7_8_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22367"},{"key":"e_1_2_7_9_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2006.164.51"},{"key":"e_1_2_7_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(94)00155-X"},{"key":"e_1_2_7_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22251"},{"key":"e_1_2_7_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-015-1651-1"},{"key":"e_1_2_7_13_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190180203"},{"key":"e_1_2_7_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480191218861"},{"key":"e_1_2_7_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480198339869"},{"key":"e_1_2_7_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(72)90045-7"},{"key":"e_1_2_7_17_1","first-page":"413","article-title":"Problems from the world surrounding perfect graphs","volume":"19","author":"Gy\u00e1rf\u00e1s A.","year":"1987","journal-title":"Zastosowania Matematyki Applicationes Math."},{"key":"e_1_2_7_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2015.10.002"},{"key":"e_1_2_7_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-018-1999-0"}],"container-title":["Journal of Graph Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/jgt.22656","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/full-xml\/10.1002\/jgt.22656","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/jgt.22656","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,1]],"date-time":"2023-09-01T17:08:53Z","timestamp":1693588133000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/jgt.22656"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,19]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["10.1002\/jgt.22656"],"URL":"https:\/\/doi.org\/10.1002\/jgt.22656","archive":["Portico"],"relation":{},"ISSN":["0364-9024","1097-0118"],"issn-type":[{"value":"0364-9024","type":"print"},{"value":"1097-0118","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,19]]},"assertion":[{"value":"2020-11-24","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-11-24","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-01-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}