{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T12:43:04Z","timestamp":1780317784102,"version":"3.54.1"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2024,7,27]],"date-time":"2024-07-27T00:00:00Z","timestamp":1722038400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,7,27]],"date-time":"2024-07-27T00:00:00Z","timestamp":1722038400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100011019","name":"Nemzeti Kutat\u00e1si Fejleszt\u00e9si \u00e9s Innov\u00e1ci\u00f3s Hivatal","doi-asserted-by":"publisher","award":["SNN129364"],"award-info":[{"award-number":["SNN129364"]}],"id":[{"id":"10.13039\/501100011019","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100011019","name":"Nemzeti Kutat\u00e1si Fejleszt\u00e9si \u00e9s Innov\u00e1ci\u00f3s Hivatal","doi-asserted-by":"publisher","award":["FK132060"],"award-info":[{"award-number":["FK132060"]}],"id":[{"id":"10.13039\/501100011019","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2024,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A 1-removed subgraph <jats:inline-formula><jats:alternatives><jats:tex-math>$$G_f$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>G<\/mml:mi>\n                    <mml:mi>f<\/mml:mi>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of a graph <jats:inline-formula><jats:alternatives><jats:tex-math>$$G=(V,E)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>G<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>V<\/mml:mi>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mi>E<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is obtained by <jats:def-list>\n                <jats:def-item>\n                  <jats:term>(i)<\/jats:term>\n                  <jats:def>\n                    <jats:p>selecting at most one edge <jats:italic>f<\/jats:italic>(<jats:italic>v<\/jats:italic>) for each vertex <jats:inline-formula><jats:alternatives><jats:tex-math>$$v\\in V$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                        <mml:mrow>\n                          <mml:mi>v<\/mml:mi>\n                          <mml:mo>\u2208<\/mml:mo>\n                          <mml:mi>V<\/mml:mi>\n                        <\/mml:mrow>\n                      <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, such that <jats:inline-formula><jats:alternatives><jats:tex-math>$$v\\in f(v)\\in E$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                        <mml:mrow>\n                          <mml:mi>v<\/mml:mi>\n                          <mml:mo>\u2208<\/mml:mo>\n                          <mml:mi>f<\/mml:mi>\n                          <mml:mo>(<\/mml:mo>\n                          <mml:mi>v<\/mml:mi>\n                          <mml:mo>)<\/mml:mo>\n                          <mml:mo>\u2208<\/mml:mo>\n                          <mml:mi>E<\/mml:mi>\n                        <\/mml:mrow>\n                      <\/mml:math><\/jats:alternatives><\/jats:inline-formula> (the mapping <jats:inline-formula><jats:alternatives><jats:tex-math>$$f:V\\rightarrow E \\cup \\{\\varnothing \\}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                        <mml:mrow>\n                          <mml:mi>f<\/mml:mi>\n                          <mml:mo>:<\/mml:mo>\n                          <mml:mi>V<\/mml:mi>\n                          <mml:mo>\u2192<\/mml:mo>\n                          <mml:mi>E<\/mml:mi>\n                          <mml:mo>\u222a<\/mml:mo>\n                          <mml:mo>{<\/mml:mo>\n                          <mml:mi>\u2205<\/mml:mi>\n                          <mml:mo>}<\/mml:mo>\n                        <\/mml:mrow>\n                      <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is allowed to be non-injective), and<\/jats:p>\n                  <\/jats:def>\n                <\/jats:def-item>\n                <jats:def-item>\n                  <jats:term>(ii)<\/jats:term>\n                  <jats:def>\n                    <jats:p>deleting all the selected edges <jats:italic>f<\/jats:italic>(<jats:italic>v<\/jats:italic>) from the edge set <jats:italic>E<\/jats:italic> of <jats:italic>G<\/jats:italic>.<\/jats:p>\n                  <\/jats:def>\n                <\/jats:def-item>\n              <\/jats:def-list><\/jats:p><jats:p> Proper vertex colorings of 1-removed subgraphs proved to be a useful tool for earlier research on some Tur\u00e1n-type problems. In this paper, we introduce a systematic investigation of the graph invariant 1-robust chromatic number, denoted as <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\chi _1(G)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msub>\n                      <mml:mi>\u03c7<\/mml:mi>\n                      <mml:mn>1<\/mml:mn>\n                    <\/mml:msub>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>G<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. This invariant is defined as the minimum chromatic number <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\chi (G_f)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03c7<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msub>\n                      <mml:mi>G<\/mml:mi>\n                      <mml:mi>f<\/mml:mi>\n                    <\/mml:msub>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> among all 1-removed subgraphs <jats:inline-formula><jats:alternatives><jats:tex-math>$$G_f$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>G<\/mml:mi>\n                    <mml:mi>f<\/mml:mi>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of <jats:italic>G<\/jats:italic>. We also examine other standard graph invariants in a similar manner.<\/jats:p>","DOI":"10.1007\/s00373-024-02817-1","type":"journal-article","created":{"date-parts":[[2024,7,27]],"date-time":"2024-07-27T16:01:39Z","timestamp":1722096099000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["The Robust Chromatic Number of Graphs"],"prefix":"10.1007","volume":"40","author":[{"given":"G\u00e1bor","family":"Bacs\u00f3","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1651-2487","authenticated-orcid":false,"given":"Bal\u00e1zs","family":"Patk\u00f3s","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zsolt","family":"Tuza","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"M\u00e1t\u00e9","family":"Vizer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2024,7,27]]},"reference":[{"issue":"17","key":"2817_CR1","doi-asserted-by":"publisher","first-page":"1933","DOI":"10.1016\/j.dam.2011.06.023","volume":"159","author":"C Bazgan","year":"2011","unstructured":"Bazgan, C., Toubaline, S., Tuza, Z.S.: The most vital nodes with respect to independent set and vertex cover. Discrete Appl. Math. 159(17), 1933\u20131946 (2011)","journal-title":"Discrete Appl. Math."},{"key":"2817_CR2","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF02760181","volume":"6","author":"G Chartrand","year":"1968","unstructured":"Chartrand, G., Kronk, H.V., Wall, C.E.: The point-arboricity of a graph. Isr. J. Math. 6, 169\u2013175 (1968)","journal-title":"Isr. J. Math."},{"issue":"1","key":"2817_CR3","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85(1), 12\u201375 (1990)","journal-title":"Inf. Comput."},{"key":"2817_CR4","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2016","unstructured":"Cygan, M., Fomin, F.V., Kowalik, \u0141, Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Cham (2016)"},{"key":"2817_CR5","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1016\/0016-0032(65)90340-6","volume":"279","author":"SL Hakimi","year":"1965","unstructured":"Hakimi, S.L.: On the degrees of the vertices of a directed graph. J. Franklin Inst. 279, 290\u2013308 (1965)","journal-title":"J. Franklin Inst."},{"issue":"1","key":"2817_CR6","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1111\/j.1749-6632.1970.tb56470.x","volume":"175","author":"F Harary","year":"1970","unstructured":"Harary, F.: Covering and packing in graphs. I. Ann. N. Y. Acad. Sci. 175(1), 198\u2013205 (1970)","journal-title":"Ann. N. Y. Acad. Sci."},{"key":"2817_CR7","unstructured":"Kardo\u0161, F., Lu\u017ear, B., Sot\u00e1k, R.: Note on robust coloring of planar graphs. Manuscript, arXiv:2401.08324"},{"key":"2817_CR8","doi-asserted-by":"crossref","unstructured":"Kemnitz, A., Voigt, M.: A note on non-4-list colorable planar graphs. Electron. J. Combin. 25(2), #P2.46 (2018)","DOI":"10.37236\/7320"},{"key":"2817_CR9","doi-asserted-by":"crossref","unstructured":"Kloks, T.: Treewidth, Computations, and Approximations. Lecture Notes in Computer Science, vol. 842. Springer, New York (1994)","DOI":"10.1007\/BFb0045375"},{"key":"2817_CR10","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/0012-365X(72)90006-4","volume":"2","author":"L Lov\u00e1sz","year":"1972","unstructured":"Lov\u00e1sz, L.: Normal hypergraphs and the perfect graph conjecture. Discrete Math. 2, 253\u2013267 (1972)","journal-title":"Discrete Math."},{"key":"2817_CR11","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/BF01580235","volume":"6","author":"M Padberg","year":"1974","unstructured":"Padberg, M.: Perfect zero-one matrices. Math. Program. 6, 180\u2013196 (1974)","journal-title":"Math. Program."},{"key":"2817_CR12","unstructured":"Patk\u00f3s, B., Tuza, Zs., Vizer, M.: Extremal graph-theoretic questions for $$q$$-ary vectors. Manuscript, arXiv:2305.01919"},{"key":"2817_CR13","doi-asserted-by":"publisher","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$$-colorable graphs. J. Combin. Theory Ser. B 16, 191\u2013193 (1974)","journal-title":"J. Combin. Theory Ser. B"},{"key":"2817_CR14","doi-asserted-by":"crossref","unstructured":"Stiebitz, M., Tuza, Zs., Voigt, M.: Orientations of graphs with prescribed weighted out-degrees. Graphs Combin. 31, 265\u2013280 (2015)","DOI":"10.1007\/s00373-013-1382-0"},{"key":"2817_CR15","unstructured":"Voigt, M.: Private communication (2023)"},{"key":"2817_CR16","doi-asserted-by":"publisher","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D Zuckerman","year":"2007","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of Max Clique and Chromatic Number. Theory Comput. 3, 103\u2013128 (2007)","journal-title":"Theory Comput."}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-024-02817-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-024-02817-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-024-02817-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,9]],"date-time":"2024-08-09T19:05:14Z","timestamp":1723230314000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-024-02817-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,27]]},"references-count":16,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,8]]}},"alternative-id":["2817"],"URL":"https:\/\/doi.org\/10.1007\/s00373-024-02817-1","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"value":"0911-0119","type":"print"},{"value":"1435-5914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,7,27]]},"assertion":[{"value":"9 May 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 February 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 July 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 July 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"89"}}