{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,4,27]],"date-time":"2024-04-27T19:12:29Z","timestamp":1714245149237},"reference-count":9,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2007,1,30]],"date-time":"2007-01-30T00:00:00Z","timestamp":1170115200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Graph Theory"],"published-print":{"date-parts":[[2007,7]]},"abstract":"Abstract<\/jats:title>The function f<\/jats:italic>(n<\/jats:italic>) is defined to be the smallest integer such that any f<\/jats:italic>(n<\/jats:italic>)\u2010chromatic digraph contains all paths with two blocks P<\/jats:italic>(k<\/jats:italic>,j<\/jats:italic>) with k<\/jats:italic> + j<\/jats:italic> = n<\/jats:italic> \u2212 1. El Sahili conjectured that f<\/jats:italic>(n<\/jats:italic>) = n<\/jats:italic>. We prove in this paper that f<\/jats:italic>(n<\/jats:italic>) \u2264 n<\/jats:italic> + 1. Our argument yields a very short and direct proof of the Gallai\u2013Roy result about directed paths. We also treat the problem under some supplementary conditions. One of them is used to give a simple proof of a result of Saks and S\u00f3s about claws. \u00a9 2007 Wiley Periodicals, Inc. J Graph Theory 55: 221\u2013226, 2007<\/jats:p>","DOI":"10.1002\/jgt.20222","type":"journal-article","created":{"date-parts":[[2007,2,3]],"date-time":"2007-02-03T00:15:26Z","timestamp":1170461726000},"page":"221-226","source":"Crossref","is-referenced-by-count":5,"title":["About paths with two blocks"],"prefix":"10.1002","volume":"55","author":[{"given":"Amine El","family":"Sahili","sequence":"first","affiliation":[]},{"given":"Mekkia","family":"Kouider","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2007,1,30]]},"reference":[{"key":"e_1_2_1_2_2","unstructured":"S. A.Burr Subtrees of directed graphs and hypergraphs In Proceedings of the Eleventh Southeastern Conference on Combinatorics Graph Theory and Computing (Florida Atlantic Univ. Boca Raton Fla.) I 28 (1980) pp.227\u2013239."},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2004.03.013"},{"key":"e_1_2_1_4_2","first-page":"115","volume-title":"On directed paths and circuits, Theory of Graphs","author":"T. Gallai","year":"1968"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-002-0483-y"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1002\/1097-0118(200012)35:4<244::AID-JGT2>3.0.CO;2-H"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1999.1945"},{"key":"e_1_2_1_8_2","first-page":"127","article-title":"Nombre chromatique et plus longs chemins d'un graphe","volume":"1","author":"B. Roy","year":"1967","journal-title":"Rev Fran\u00e7aise Automat Informat Recherche Op\u00e9rationelle S\u00e9r Rouge"},{"key":"e_1_2_1_9_2","first-page":"663","article-title":"On unavoidable subgraphs of tournaments in finite and infinite sets","volume":"37","author":"M. Saks","year":"1981","journal-title":"Colloquia Mathematica Societatis J\u00e1nos Bolyai"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.2307\/2000567"}],"container-title":["Journal of Graph Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fjgt.20222","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/jgt.20222","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,18]],"date-time":"2023-10-18T19:15:33Z","timestamp":1697656533000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/jgt.20222"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,1,30]]},"references-count":9,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2007,7]]}},"alternative-id":["10.1002\/jgt.20222"],"URL":"https:\/\/doi.org\/10.1002\/jgt.20222","archive":["Portico"],"relation":{},"ISSN":["0364-9024","1097-0118"],"issn-type":[{"value":"0364-9024","type":"print"},{"value":"1097-0118","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,1,30]]}}}