{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T16:04:29Z","timestamp":1762272269867,"version":"3.37.3"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2018,5,19]],"date-time":"2018-05-19T00:00:00Z","timestamp":1526688000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2018,7]]},"DOI":"10.1007\/s00373-018-1903-y","type":"journal-article","created":{"date-parts":[[2018,5,19]],"date-time":"2018-05-19T08:49:57Z","timestamp":1526719797000},"page":"647-668","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Triangle Packings and Transversals of Some $$K_{4}$$ K 4 -Free Graphs"],"prefix":"10.1007","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1509-8832","authenticated-orcid":false,"given":"Andrea","family":"Munaro","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,5,19]]},"reference":[{"issue":"1","key":"1903_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s004930170001","volume":"21","author":"R Aharoni","year":"2001","unstructured":"Aharoni, R.: Ryser\u2019s conjecture for tripartite $$3$$ 3 -graphs. Combinatorica 21(1), 1\u20134 (2001)","journal-title":"Combinatorica"},{"issue":"17","key":"1903_CR2","doi-asserted-by":"publisher","first-page":"2627","DOI":"10.1016\/j.disc.2011.11.037","volume":"312","author":"P Anand","year":"2012","unstructured":"Anand, P., Escuadro, H., Gera, R., Hartke, S.G., Stolee, D.: On the hardness of recognizing triangular line graphs. Discret. Math. 312(17), 2627\u20132638 (2012)","journal-title":"Discret. Math."},{"issue":"2","key":"1903_CR3","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/S0021-9800(70)80019-9","volume":"9","author":"LW Beineke","year":"1970","unstructured":"Beineke, L.W.: Characterizations of derived graphs. J. Comb. Theory 9(2), 129\u2013135 (1970)","journal-title":"J. Comb. Theory"},{"issue":"1\u20132","key":"1903_CR4","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/S0166-218X(03)00266-X","volume":"138","author":"A Brandst\u00e4dt","year":"2004","unstructured":"Brandst\u00e4dt, A.: ( $${P}_{5}$$ P 5 , diamond)-free graphs revisited: structure and linear time optimization. Discret. Appl. Math. 138(1\u20132), 13\u201327 (2004)","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"1903_CR5","doi-asserted-by":"publisher","first-page":"51","DOI":"10.4007\/annals.2006.164.51","volume":"164","author":"M Chudnovsky","year":"2006","unstructured":"Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R.: The strong perfect graph theorem. Ann. Math. 164(1), 51\u2013229 (2006)","journal-title":"Ann. Math."},{"issue":"3","key":"1903_CR6","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/j.jctb.2009.10.001","volume":"100","author":"M Chudnovsky","year":"2010","unstructured":"Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R.: $${K}_{4}$$ K 4 -free graphs with no odd holes. J. Comb. Theory Ser. B 100(3), 313\u2013331 (2010)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"2","key":"1903_CR7","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0012-365X(86)90156-1","volume":"58","author":"M Conforti","year":"1986","unstructured":"Conforti, M., Corneil, D.G., Mahjoub, A.R.: $${K}_{i}$$ K i -covers I: complexity and polytopes. Discret. Math. 58(2), 121\u2013142 (1986)","journal-title":"Discret. Math."},{"issue":"4","key":"1903_CR8","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1002\/jgt.3190110415","volume":"11","author":"M Conforti","year":"1987","unstructured":"Conforti, M., Corneil, D.C., Mahjoub, A.R.: $${K}_{i}$$ K i -covers. II. $${K}_{i}$$ K i -perfect graphs. J. Graph Theory 11(4), 569\u2013584 (1987)","journal-title":"J. Graph Theory"},{"issue":"4","key":"1903_CR9","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0012-365X(74)90150-2","volume":"8","author":"CR Cook","year":"1974","unstructured":"Cook, C.R.: Two characterizations of interchange graphs of complete $$m$$ m -partite graphs. Discret. Math. 8(4), 305\u2013311 (1974)","journal-title":"Discret. Math."},{"key":"1903_CR10","doi-asserted-by":"publisher","first-page":"34","DOI":"10.4153\/CJM-1959-003-9","volume":"11","author":"P Erd\u0151s","year":"1959","unstructured":"Erd\u0151s, P.: Graph theory and probability. Can. J. Math. 11, 34\u201338 (1959)","journal-title":"Can. J. Math."},{"issue":"1","key":"1903_CR11","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1006\/jctb.1995.1043","volume":"65","author":"K Fraughnaugh","year":"1995","unstructured":"Fraughnaugh, K., Locke, S.C.: $$11\/30$$ 11 \/ 30 (Finding large independent sets in connected triangle-free $$3$$ 3 -regular graphs). J. Comb. Theory Ser. B 65(1), 51\u201372 (1995)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"1903_CR12","first-page":"3","volume":"39","author":"D Fron\u010dek","year":"1989","unstructured":"Fron\u010dek, D.: Locally linear graphs. Math. Slovaca 39(1), 3\u20136 (1989)","journal-title":"Math. Slovaca"},{"key":"1903_CR13","first-page":"373","volume":"8","author":"T Gallai","year":"1963","unstructured":"Gallai, T.: Kritische graphen II. A Magyar Tudom\u00e1nyos Akad\u00e9mia Matematikai Kutat\u00f3 Int\u00e9zet\u00e9nek K\u00f6zlem\u00e9nyei 8, 373\u2013395 (1963)","journal-title":"A Magyar Tudom\u00e1nyos Akad\u00e9mia Matematikai Kutat\u00f3 Int\u00e9zet\u00e9nek K\u00f6zlem\u00e9nyei"},{"issue":"1","key":"1903_CR14","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/BF02020961","volume":"18","author":"T Gallai","year":"1967","unstructured":"Gallai, T.: Transitiv orientierbare graphen. Acta Mathematica Academiae Scientiarum Hungarica 18(1), 25\u201366 (1967)","journal-title":"Acta Mathematica Academiae Scientiarum Hungarica"},{"issue":"3\u20134","key":"1903_CR15","first-page":"413","volume":"19","author":"A Gy\u00e1rf\u00e1s","year":"1987","unstructured":"Gy\u00e1rf\u00e1s, A.: Problems from the world surrounding perfect graphs. Zastosowania Matematyki 19(3\u20134), 413\u2013441 (1987)","journal-title":"Zastosowania Matematyki"},{"issue":"5","key":"1903_CR16","doi-asserted-by":"publisher","first-page":"1155","DOI":"10.1016\/j.jctb.2012.06.001","volume":"102","author":"A Gy\u00e1rf\u00e1s","year":"2012","unstructured":"Gy\u00e1rf\u00e1s, A., Seb\u0151, A., Trotignon, N.: The chromatic gap and its extremes. J. Comb. Theory Ser. B 102(5), 1155\u20131178 (2012)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"3","key":"1903_CR17","first-page":"299","volume":"4","author":"A Gy\u00e1rf\u00e1s","year":"2013","unstructured":"Gy\u00e1rf\u00e1s, A., Li, Z., Machado, R., Seb\u0151, A., Thomass\u00e9, S., Trotignon, N.: Complements of nearly perfect graphs. J. Comb. 4(3), 299\u2013310 (2013)","journal-title":"J. Comb."},{"issue":"5","key":"1903_CR18","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1007\/s00373-011-1071-9","volume":"28","author":"P Haxell","year":"2012","unstructured":"Haxell, P., Kostochka, A., Thomass\u00e9, S.: Packing and covering triangles in $${K}_{4}$$ K 4 -free planar graphs. Graphs Comb. 28(5), 653\u2013662 (2012)","journal-title":"Graphs Comb."},{"issue":"1\u20133","key":"1903_CR19","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0012-365X(98)00183-6","volume":"195","author":"PE Haxell","year":"1999","unstructured":"Haxell, P.E.: Packing and covering triangles in graphs. Discret. Math. 195(1\u20133), 251\u2013254 (1999)","journal-title":"Discret. Math."},{"issue":"5","key":"1903_CR20","doi-asserted-by":"publisher","first-page":"799","DOI":"10.1016\/j.ejc.2011.09.024","volume":"33","author":"PE Haxell","year":"2012","unstructured":"Haxell, P.E., Kostochka, A.V., Thomass\u00e9, S.: A stability theorem on fractional covering of triangles by edges. Eur. J. Comb. 33(5), 799\u2013806 (2012)","journal-title":"Eur. J. Comb."},{"issue":"15","key":"1903_CR21","doi-asserted-by":"publisher","first-page":"3169","DOI":"10.1016\/j.disc.2007.06.044","volume":"308","author":"CC Heckman","year":"2008","unstructured":"Heckman, C.C.: On the tightness of the $$\\frac{5}{14}$$ 5 14 independence ratio. Discret. Math. 308(15), 3169\u20133179 (2008)","journal-title":"Discret. Math."},{"key":"1903_CR22","unstructured":"Henderson, J.R.: Permutation decomposition of $$(0,1)$$ ( 0 , 1 ) -matrices and decomposition transversals. Ph.D. thesis, California Institute of Technology (1971)"},{"issue":"11","key":"1903_CR23","doi-asserted-by":"publisher","first-page":"1900","DOI":"10.1016\/j.disc.2012.03.002","volume":"312","author":"MA Henning","year":"2012","unstructured":"Henning, M.A., L\u00f6wenstein, C., Rautenbach, D.: Independent sets and matchings in subcubic graphs. Discret. Math. 312(11), 1900\u20131910 (2012)","journal-title":"Discret. Math."},{"key":"1903_CR24","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22258","author":"CT Ho\u00e0ng","year":"2018","unstructured":"Ho\u00e0ng, C.T.: On the structure of (banner, odd hole)-free graphs. J. Graph Theory (2018). https:\/\/doi.org\/10.1002\/jgt.22258","journal-title":"J. Graph Theory"},{"key":"1903_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.disc.2014.01.006","volume":"323","author":"F Joos","year":"2014","unstructured":"Joos, F.: Independence and matching number in graphs with maximum degree 4. Discret. Math. 323, 1\u20136 (2014)","journal-title":"Discret. Math."},{"issue":"1\u20133","key":"1903_CR26","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/0012-365X(93)00228-W","volume":"142","author":"M Krivelevich","year":"1995","unstructured":"Krivelevich, M.: On a conjecture of Tuza about packing and covering of triangles. Discret. Math. 142(1\u20133), 281\u2013286 (1995)","journal-title":"Discret. Math."},{"issue":"3","key":"1903_CR27","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1007\/s00373-011-1048-8","volume":"28","author":"SA Lakshmanan","year":"2012","unstructured":"Lakshmanan, S.A., Bujt\u00e1s, C., Tuza, Z.: Small edge sets meeting all triangles of a graph. Graphs Comb. 28(3), 381\u2013392 (2012)","journal-title":"Graphs Comb."},{"issue":"3","key":"1903_CR28","doi-asserted-by":"crossref","first-page":"P3.33","DOI":"10.37236\/3983","volume":"22","author":"SA Lakshmanan","year":"2015","unstructured":"Lakshmanan, S.A., Bujt\u00e1s, C., Tuza, Z.: Generalized line graphs: Cartesian products and complexity of recognition. Electron. J. Comb. 22(3), P3.33 (2015)","journal-title":"Electron. J. Comb."},{"key":"1903_CR29","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1016\/j.dam.2015.12.012","volume":"209","author":"SA Lakshmanan","year":"2016","unstructured":"Lakshmanan, S.A., Bujt\u00e1s, C., Tuza, Z.: Induced cycles in triangle graphs. Discret. Appl. Math. 209, 264\u2013275 (2016)","journal-title":"Discret. Appl. Math."},{"issue":"1\u20133","key":"1903_CR30","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/0012-365X(95)00109-A","volume":"159","author":"VB Le","year":"1996","unstructured":"Le, V.B.: Gallai graphs and anti-Gallai graphs. Discret. Math. 159(1\u20133), 179\u2013189 (1996)","journal-title":"Discret. Math."},{"issue":"2","key":"1903_CR31","first-page":"193","volume":"10","author":"VB Le","year":"1994","unstructured":"Le, V.B., Prisner, E.: Iterated $$k$$ k -line graphs. Graphs Comb. 10(2), 193\u2013203 (1994)","journal-title":"Graphs Comb."},{"issue":"4","key":"1903_CR32","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1145\/321850.321853","volume":"21","author":"PGH Lehot","year":"1974","unstructured":"Lehot, P.G.H.: An optimal algorithm to detect a line graph and output its root graph. J. ACM 21(4), 569\u2013575 (1974)","journal-title":"J. ACM"},{"issue":"9","key":"1903_CR33","doi-asserted-by":"publisher","first-page":"2208","DOI":"10.1016\/j.disc.2017.04.004","volume":"340","author":"A Munaro","year":"2017","unstructured":"Munaro, A.: Bounded clique cover of some sparse graphs. Discret. Math. 340(9), 2208\u20132216 (2017)","journal-title":"Discret. Math."},{"key":"1903_CR34","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/j.ejc.2015.03.006","volume":"49","author":"GJ Puleo","year":"2015","unstructured":"Puleo, G.J.: Tuza\u2019s Conjecture for graphs with maximum average degree less than $$7$$ 7 . Eur. J. Comb. 49, 134\u2013152 (2015)","journal-title":"Eur. J. Comb."},{"key":"1903_CR35","unstructured":"Radziszowski, S.P.: Small Ramsey numbers. Electron. J. Comb. DS1 (2014)"},{"issue":"4","key":"1903_CR36","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1016\/0020-0190(73)90029-X","volume":"2","author":"ND Roussopoulos","year":"1973","unstructured":"Roussopoulos, N.D.: A max $$\\{m, n\\}$$ { m , n } algorithm for determining the graph $${H}$$ H from its line graph $${G}$$ G . Inf. Process. Lett. 2(4), 108\u2013112 (1973)","journal-title":"Inf. Process. Lett."},{"key":"1903_CR37","unstructured":"Scott, A., Seymour, P.: Induced subgraphs of graphs with large chromatic number. I. Odd holes. J. Comb. Theory Ser. B 121, 68\u201384 (2016)"},{"key":"1903_CR38","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1090\/S0002-9947-1979-0546922-6","volume":"256","author":"W Staton","year":"1979","unstructured":"Staton, W.: Some Ramsey-type numbers and the independence ratio. Trans. Am. Math. Soc. 256, 353\u2013370 (1979)","journal-title":"Trans. Am. Math. Soc."},{"issue":"2","key":"1903_CR39","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0095-8956(03)00069-8","volume":"89","author":"M Stehl\u00edk","year":"2003","unstructured":"Stehl\u00edk, M.: Critical graphs with connected complements. J. Comb. Theory Ser. B 89(2), 189\u2013194 (2003)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"4","key":"1903_CR40","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/BF01787705","volume":"6","author":"Z Tuza","year":"1990","unstructured":"Tuza, Z.: A conjecture on triangles of graphs. Graphs Comb. 6(4), 373\u2013380 (1990)","journal-title":"Graphs Comb."},{"key":"1903_CR41","volume-title":"Introduction to Graph Theory","author":"DB West","year":"2001","unstructured":"West, D.B.: Introduction to Graph Theory, 2nd edn. Prentice Hall, Upper Saddle River (2001)","edition":"2"}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00373-018-1903-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-018-1903-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-018-1903-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,2]],"date-time":"2020-11-02T05:23:22Z","timestamp":1604294602000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00373-018-1903-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,5,19]]},"references-count":41,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,7]]}},"alternative-id":["1903"],"URL":"https:\/\/doi.org\/10.1007\/s00373-018-1903-y","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"type":"print","value":"0911-0119"},{"type":"electronic","value":"1435-5914"}],"subject":[],"published":{"date-parts":[[2018,5,19]]},"assertion":[{"value":"10 December 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 April 2018","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 May 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}