{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T01:20:36Z","timestamp":1777425636791,"version":"3.51.4"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2017,12,9]],"date-time":"2017-12-09T00:00:00Z","timestamp":1512777600000},"content-version":"unspecified","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,1]]},"DOI":"10.1007\/s00373-017-1864-6","type":"journal-article","created":{"date-parts":[[2017,12,9]],"date-time":"2017-12-09T11:17:58Z","timestamp":1512818278000},"page":"109-128","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Star Coloring of Certain Graph Classes"],"prefix":"10.1007","volume":"34","author":[{"given":"T.","family":"Karthick","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,12,9]]},"reference":[{"key":"1864_CR1","doi-asserted-by":"crossref","first-page":"#R26","DOI":"10.37236\/1779","volume":"11","author":"MO Albertson","year":"2004","unstructured":"Albertson, M.O., Chappell, G.G., Kierstead, H.A., K\u00fcndgen, A., Ramamurthi, R.: Coloring with no 2-colored $$P_4$$ P 4 \u2019s. Electron. J. Combin 11, #R26 (2004)","journal-title":"Electron. J. Combin"},{"key":"1864_CR2","doi-asserted-by":"crossref","first-page":"911","DOI":"10.1016\/j.disc.2011.02.021","volume":"311","author":"NR Aravind","year":"2011","unstructured":"Aravind, N.R., Karthick, T., Subramanian, C.R.: Bounding $$\\chi $$ \u03c7 in terms of $$\\omega $$ \u03c9 and $$\\Delta $$ \u0394 for some classes of graphs. Discrete Math. 311, 911\u2013920 (2011)","journal-title":"Discrete Math."},{"key":"1864_CR3","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/0012-365X(93)90477-B","volume":"115","author":"Z Bl\u00e1zsik","year":"1993","unstructured":"Bl\u00e1zsik, Z., Hujter, M., Pluh\u00e1r, A., Tuza, Zs: Graphs with no induced $$C_4$$ C 4 and $$2K_2$$ 2 K 2 . Discrete Math. 115, 51\u201355 (1993)","journal-title":"Discrete Math."},{"key":"1864_CR4","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph classes: a survey. In: SIAM Monographs on Discrete Mathematics. SIAM, Philadelphia (1999)","DOI":"10.1137\/1.9780898719796"},{"key":"1864_CR5","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/S0166-218X(03)00389-5","volume":"132","author":"A Brandst\u00e4dt","year":"2004","unstructured":"Brandst\u00e4dt, A., Mosca, R.: On the structure and stability number of $$P_5$$ P 5 - and co-chair-free graphs. Discrete Appl. Math. 132, 47\u201365 (2004)","journal-title":"Discrete Appl. Math."},{"key":"1864_CR6","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1002\/jgt.21636","volume":"72","author":"M Chen","year":"2013","unstructured":"Chen, M., Raspaud, A., Wang, W.: 6-Star-coloring of subcubic graphs. J. Graph Theory 72, 128\u2013145 (2013)","journal-title":"J. Graph Theory"},{"issue":"4","key":"1864_CR7","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1002\/jgt.20212","volume":"54","author":"SA Choudum","year":"2007","unstructured":"Choudum, S.A., Karthick, T., Shalu, M.A.: Perfect coloring and linearly $$\\chi $$ \u03c7 -bounded $$P_6$$ P 6 -free graphs. J. Graph Theory 54(4), 293\u2013306 (2007)","journal-title":"J. Graph Theory"},{"key":"1864_CR8","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1007\/s00373-008-0801-0","volume":"24","author":"SA Choudum","year":"2008","unstructured":"Choudum, S.A., Karthick, T., Shalu, M.A.: Linear chromatic bounds for a subfamily of $$3K_1$$ 3 K 1 -free graphs. Graphs Combin. 24, 413\u2013428 (2008)","journal-title":"Graphs Combin."},{"key":"1864_CR9","first-page":"111","volume":"32","author":"SA Choudum","year":"2005","unstructured":"Choudum, S.A., Shalu, M.A.: The class of $$\\{3K_1, C_4\\}$$ { 3 K 1 , C 4 } -free graphs. Australas. J. Combin. 32, 111\u2013116 (2005)","journal-title":"Australas. J. Combin."},{"key":"1864_CR10","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1002\/jgt.21732","volume":"75","author":"M Chudnovsky","year":"2014","unstructured":"Chudnovsky, M., Plumettaz, M.: The structure of claw-free perfect graphs. J. Graph Theory 75, 203\u2013230 (2014)","journal-title":"J. Graph Theory"},{"issue":"1","key":"1864_CR11","doi-asserted-by":"crossref","first-page":"51","DOI":"10.4007\/annals.2006.164.51","volume":"164","author":"M Chudnovsky","year":"2006","unstructured":"Chudnovsky, M., Seymour, P., Robertson, N., Thomas, R.: The strong perfect graph theorem. Ann. Math. 164(1), 51\u2013229 (2006)","journal-title":"Ann. Math."},{"key":"1864_CR12","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/s00236-007-0064-x","volume":"45","author":"I Cie\u015blik","year":"2008","unstructured":"Cie\u015blik, I.: On-line coloring of $$P_5$$ P 5 -free graphs. Acta Inform. 45, 79\u201391 (2008)","journal-title":"Acta Inform."},{"key":"1864_CR13","doi-asserted-by":"crossref","first-page":"346","DOI":"10.4153\/CJM-1961-029-9","volume":"13","author":"P Erd\u00f6s","year":"1961","unstructured":"Erd\u00f6s, P.: Graph theory and probability II. Can. J. Math. 13, 346\u2013352 (1961)","journal-title":"Can. J. Math."},{"key":"1864_CR14","doi-asserted-by":"crossref","unstructured":"Fertin, G., Raspaud, A., Reed, B.A.: Star coloring of graphs. In: 27th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2001), Lecture Notes in Computer Science, vol. 2204, pp. 140\u2013153 (2001)","DOI":"10.1007\/3-540-45477-2_14"},{"issue":"3","key":"1864_CR15","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1002\/jgt.20029","volume":"47","author":"G Fertin","year":"2007","unstructured":"Fertin, G., Raspaud, A., Reed, B.A.: J. Graph Theory 47(3), 163\u2013182 (2007)","journal-title":"J. Graph Theory"},{"key":"1864_CR16","unstructured":"F\u00f6ldes, S., Hammer, P.L.: Split graphs. In: Proceedings of the Eighth Southeastern Conference on Combinatorics. Graph Theory and Computing. Congressus Numerantium, vol. XIX. Utilitas Math., Winnipeg, pp. 311\u2013315 (1977)"},{"key":"1864_CR17","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/0012-365X(94)00155-X","volume":"146","author":"JL Fouquet","year":"1995","unstructured":"Fouquet, J.L., Giakoumakis, V., Maire, F., Thuillier, H.: On graphs without $$P_5$$ P 5 and $$\\overline{P_5}$$ P 5 \u00af . Discrete Math. 146, 33\u201344 (1995)","journal-title":"Discrete Math."},{"key":"1864_CR18","unstructured":"Gaspers, S., Huang, S.: Linearly $$\\chi $$ \u03c7 -bounding ( $$P_6, C_4$$ P 6 , C 4 )-free graphs. (2017). arXiv:1709.09750"},{"issue":"4","key":"1864_CR19","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1137\/S0036144504444711","volume":"47","author":"AH Gebremedhin","year":"2005","unstructured":"Gebremedhin, A.H., Manne, F., Pothen, A.: What color is your Jacobian? Graph coloring for computing derivatives. SIAM Rev. 47(4), 629\u2013705 (2005)","journal-title":"SIAM Rev."},{"key":"1864_CR20","doi-asserted-by":"crossref","first-page":"1042","DOI":"10.1137\/050639879","volume":"29","author":"AH Gebremedhin","year":"2007","unstructured":"Gebremedhin, A.H., Tarafdar, A., Manne, F., Pothen, A.: New acyclic and star coloring algorithms with applications to computing Hessians. SIAM J. Sci. Comput. 29, 1042\u20131072 (2007)","journal-title":"SIAM J. Sci. Comput."},{"issue":"1","key":"1864_CR21","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0012-365X(78)90178-4","volume":"24","author":"MC Golumbic","year":"1978","unstructured":"Golumbic, M.C.: Trivially perfect graphs. Discrete Math. 24(1), 105\u2013107 (1978)","journal-title":"Discrete Math."},{"key":"1864_CR22","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/S0012-365X(03)00197-3","volume":"272","author":"S Gravier","year":"2003","unstructured":"Gravier, S., Ho\u00e0ng, C.T., Maffray, F.: Coloring the hypergraph of maximal cliques of a graph with no long path. Discrete Math. 272, 285\u2013290 (2003)","journal-title":"Discrete Math."},{"key":"1864_CR23","doi-asserted-by":"crossref","first-page":"390","DOI":"10.1007\/BF02764716","volume":"14","author":"B Gr\u00fcnbaum","year":"1973","unstructured":"Gr\u00fcnbaum, B.: Acyclic colorings of planar graphs. Isr. J. Math. 14, 390\u2013408 (1973)","journal-title":"Isr. J. Math."},{"key":"1864_CR24","first-page":"413","volume":"19","author":"A Gy\u00e1rf\u00e1s","year":"1987","unstructured":"Gy\u00e1rf\u00e1s, A.: Problems from the world surrounding perfect graphs. Zastos. Mat. Appl. Math. 19, 413\u2013441 (1987)","journal-title":"Zastos. Mat. Appl. Math."},{"issue":"2","key":"1864_CR25","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/BF01206361","volume":"11","author":"A Gy\u00e1rf\u00e1s","year":"1991","unstructured":"Gy\u00e1rf\u00e1s, A., Lehel, J.: Effective on-line coloring of $$P_5$$ P 5 -free graphs. Combinatorica 11(2), 181\u2013184 (1991)","journal-title":"Combinatorica"},{"key":"1864_CR26","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1016\/j.dam.2015.01.022","volume":"186","author":"CT Ho\u00e1ng","year":"2015","unstructured":"Ho\u00e1ng, C.T., Lazzarato, D.A.: Polynomial-time algorithms for minimum weighted colorings of ( $$P_5, \\overline{P}_{5}$$ P 5 , P \u00af 5 )-free graphs and similar graph classes. Discrete Appl. Math. 186, 106\u2013111 (2015)","journal-title":"Discrete Appl. Math."},{"key":"1864_CR27","volume-title":"Graph Coloring Problems","author":"TR Jensen","year":"1995","unstructured":"Jensen, T.R., Toft, B.: Graph Coloring Problems. Wiley-Interscience, New York (1995)"},{"key":"1864_CR28","doi-asserted-by":"crossref","unstructured":"Karthick, T.: Star chromatic bounds. In: Proceedings of International Conference on Graph Theory and its Applications (ICGTA 2015). Electron. Notes Discrete Math. 53, 413\u2013419 (2016)","DOI":"10.1016\/j.endm.2016.05.035"},{"issue":"2","key":"1864_CR29","doi-asserted-by":"crossref","first-page":"373","DOI":"10.7151\/dmgt.1672","volume":"33","author":"T Karthick","year":"2013","unstructured":"Karthick, T., Subramanian, C.R.: Star coloring of subcubic graphs. Discuss. Math. Graph Theory 33(2), 373\u2013385 (2013)","journal-title":"Discuss. Math. Graph Theory"},{"key":"1864_CR30","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1137\/060674211","volume":"24","author":"K Kawarabayashi","year":"2010","unstructured":"Kawarabayashi, K., Mohar, B.: Star coloring and acyclic coloring of locally planar graphs. SIAM J. Discrete Math. 24, 56\u201371 (2010)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"1864_CR31","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/jgt.20342","volume":"60","author":"HA Kierstead","year":"2009","unstructured":"Kierstead, H.A., K\u00fcndgen, A., Timmons, C.: Star coloring bipartite planar graphs. J. Graph Theory 60(1), 1\u201310 (2009)","journal-title":"J. Graph Theory"},{"key":"1864_CR32","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0095-8956(72)90045-7","volume":"13","author":"L Lov\u00e1sz","year":"1972","unstructured":"Lov\u00e1sz, L.: A characterization of perfect graphs. J. Combin. Theory Ser. B 13, 95\u201398 (1972)","journal-title":"J. Combin. Theory Ser. B"},{"key":"1864_CR33","doi-asserted-by":"crossref","first-page":"1842","DOI":"10.1016\/j.dam.2011.04.011","volume":"159","author":"A Lyons","year":"2011","unstructured":"Lyons, A.: Acyclic and star colorings of graphs. Discrete Appl. Math. 159, 1842\u20131850 (2011)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"1864_CR34","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1016\/0166-218X(94)00022-0","volume":"52","author":"F Maffray","year":"1994","unstructured":"Maffray, F., Preissmann, M.: Linear recognition of pseudo-split graphs. Discrete Appl. Math. 52(3), 307\u2013312 (1994)","journal-title":"Discrete Appl. Math."},{"key":"1864_CR35","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1006\/jctb.1998.1872","volume":"75","author":"F Maffray","year":"1999","unstructured":"Maffray, F., Reed, B.A.: A description of claw-free perfect graphs. J. Combin. Theory Ser. B 75, 134\u2013156 (1999)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"3","key":"1864_CR36","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1016\/j.ejc.2011.09.007","volume":"33","author":"B Mohar","year":"2012","unstructured":"Mohar, B., Spacapan, S.: Degenerate and star colorings of graphs on surfaces. Eur. J. Combin. 33(3), 340\u2013349 (2012)","journal-title":"Eur. J. Combin."},{"key":"1864_CR37","doi-asserted-by":"crossref","first-page":"651","DOI":"10.1007\/978-3-642-55566-4_29","volume-title":"Discrete and Computational Geometry: The GoodmanPollack Festschrift","author":"J Ne\u0161et\u0159il","year":"2003","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Colorings and homomorphisms of minor closed classes. In: Aronov, B., Basu, S., Pach, J., Sharir, M. (eds.) Discrete and Computational Geometry: The GoodmanPollack Festschrift, pp. 651\u2013664. Springer, New York (2003)"},{"issue":"4","key":"1864_CR38","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1007\/s00493-009-2257-0","volume":"29","author":"A P\u00f3r","year":"2009","unstructured":"P\u00f3r, A., Wood, D.R.: Colourings of the cartesian product of graphs and multiplicative sidon sets. Combinatorica 29(4), 449\u2013466 (2009)","journal-title":"Combinatorica"},{"key":"1864_CR39","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00373-003-0540-1","volume":"20","author":"B Randerath","year":"2004","unstructured":"Randerath, B., Schiermeyer, I.: Vertex colouring and forbidden subgraphs\u2014a survey. Graphs Combin. 20, 1\u201340 (2004)","journal-title":"Graphs Combin."},{"key":"1864_CR40","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1002\/(SICI)1097-0118(199804)27:4<177::AID-JGT1>3.0.CO;2-K","volume":"27","author":"B Reed","year":"1998","unstructured":"Reed, B.: $$\\omega, \\varDelta $$ \u03c9 , \u0394 and $$\\chi $$ \u03c7 . J. Graph Theory 27, 177\u2013212 (1998)","journal-title":"J. Graph Theory"},{"key":"1864_CR41","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/0095-8956(74)90063-X","volume":"16","author":"D Seinsche","year":"1974","unstructured":"Seinsche, D.: On a property of the class of $$n$$ n -colorable graphs. J. Combin. Theory Ser. B 16, 191\u2013193 (1974)","journal-title":"J. Combin. Theory Ser. B"},{"key":"1864_CR42","doi-asserted-by":"crossref","first-page":"2121","DOI":"10.1007\/s00373-016-1702-2","volume":"32","author":"MA Shalu","year":"2016","unstructured":"Shalu, M.A., Sandhya, T.P.: Star coloring of graphs with girth at least five. Graphs Combin. 32, 2121\u20132134 (2016)","journal-title":"Graphs Combin."},{"key":"1864_CR43","doi-asserted-by":"crossref","first-page":"#R124","DOI":"10.37236\/848","volume":"15","author":"C Timmons","year":"2008","unstructured":"Timmons, C.: Star coloring high girth planar graphs. Electron. J. Combin 15, #R124 (2008)","journal-title":"Electron. J. Combin"},{"key":"1864_CR44","volume-title":"Introduction to Graph Theory","author":"DB West","year":"2000","unstructured":"West, D.B.: Introduction to Graph Theory, 2nd edn. Prentice-Hall, Englewood Cliffs (2000)","edition":"2"},{"key":"1864_CR45","first-page":"37","volume":"7","author":"DA Wood","year":"2005","unstructured":"Wood, D.A.: Acyclic, star and oriented colourings of graph subdivisions. Discrete Math. Theor. Comput. Sci. 7, 37\u201350 (2005)","journal-title":"Discrete Math. Theor. Comput. Sci."}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00373-017-1864-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-017-1864-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-017-1864-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,24]],"date-time":"2020-10-24T02:40:50Z","timestamp":1603507250000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00373-017-1864-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,9]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["1864"],"URL":"https:\/\/doi.org\/10.1007\/s00373-017-1864-6","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"value":"0911-0119","type":"print"},{"value":"1435-5914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,12,9]]}}}