{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:05:28Z","timestamp":1740107128717,"version":"3.37.3"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2024,10,8]],"date-time":"2024-10-08T00:00:00Z","timestamp":1728345600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,10,8]],"date-time":"2024-10-08T00:00:00Z","timestamp":1728345600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100015774","name":"University of Malta","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100015774","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2024,12]]},"abstract":"Abstract<\/jats:title>\n It is proved that for integers b<\/jats:italic>,\u00a0r<\/jats:italic> such that \n \n $$3 \\le b < r \\le \\left( {\\begin{array}{c}b+1\\\\ 2\\end{array}}\\right) - 1$$<\/jats:tex-math>\n \n \n 3<\/mml:mn>\n \u2264<\/mml:mo>\n b<\/mml:mi>\n <<\/mml:mo>\n r<\/mml:mi>\n \u2264<\/mml:mo>\n \n \n \n \n \n \n b<\/mml:mi>\n +<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:mtd>\n <\/mml:mtr>\n \n \n \n \n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:mtd>\n <\/mml:mtr>\n <\/mml:mtable>\n <\/mml:mrow>\n <\/mml:mfenced>\n -<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, there exists a red\/blue edge-colored graph such that the red degree of every vertex is r<\/jats:italic>, the blue degree of every vertex is b<\/jats:italic>, yet in the closed neighbourhood of every vertex there are more blue edges than red edges. The upper bound \n \n $$r \\le \\left( {\\begin{array}{c}b+1\\\\ 2\\end{array}}\\right) -1$$<\/jats:tex-math>\n \n \n r<\/mml:mi>\n \u2264<\/mml:mo>\n \n \n \n \n \n \n b<\/mml:mi>\n +<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:mtd>\n <\/mml:mtr>\n \n \n \n \n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:mtd>\n <\/mml:mtr>\n <\/mml:mtable>\n <\/mml:mrow>\n <\/mml:mfenced>\n -<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> is best possible for any \n \n $$b \\ge 3$$<\/jats:tex-math>\n \n \n b<\/mml:mi>\n \u2265<\/mml:mo>\n 3<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. We further extend this theorem to more than two colours, and to larger neighbourhoods. A useful result required in some of our proofs, of independent interest, is that for integers r<\/jats:italic>,\u00a0t<\/jats:italic> such that \n \n $$0 \\le t \\le \\frac{r^2}{2} - 5r^{3\/2}$$<\/jats:tex-math>\n \n \n 0<\/mml:mn>\n \u2264<\/mml:mo>\n t<\/mml:mi>\n \u2264<\/mml:mo>\n \n \n r<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n 2<\/mml:mn>\n <\/mml:mfrac>\n -<\/mml:mo>\n 5<\/mml:mn>\n \n r<\/mml:mi>\n \n 3<\/mml:mn>\n \/<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, there exists an r<\/jats:italic>-regular graph in which each open neighbourhood induces precisely t<\/jats:italic> edges. Several explicit constructions are introduced and relationships with constant linked graphs, (r<\/jats:italic>,\u00a0b<\/jats:italic>)-regular graphs and vertex transitive graphs are revealed.<\/jats:p>","DOI":"10.1007\/s00373-024-02838-w","type":"journal-article","created":{"date-parts":[[2024,10,8]],"date-time":"2024-10-08T04:01:52Z","timestamp":1728360112000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Flip colouring of graphs"],"prefix":"10.1007","volume":"40","author":[{"given":"Yair","family":"Caro","sequence":"first","affiliation":[]},{"given":"Josef","family":"Lauri","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4391-2988","authenticated-orcid":false,"given":"Xandru","family":"Mifsud","sequence":"additional","affiliation":[]},{"given":"Raphael","family":"Yuster","sequence":"additional","affiliation":[]},{"given":"Christina","family":"Zarb","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,10,8]]},"reference":[{"key":"2838_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.dam.2014.07.026","volume":"180","author":"MA Abdullah","year":"2015","unstructured":"Abdullah, M.A., Draief, M.: Global majority consensus by local majority polling on graphs of a given degree sequence. Discrete Appl. Math. 180, 1\u201310 (2015)","journal-title":"Discrete Appl. Math."},{"issue":"6","key":"2838_CR2","doi-asserted-by":"publisher","first-page":"1469","DOI":"10.1007\/s00373-018-1938-0","volume":"34","author":"Y Caro","year":"2018","unstructured":"Caro, Y., Yuster, R.: The effect of local majority on global majority in connected graphs. Graphs and Combinatorics 34(6), 1469\u20131487 (2018)","journal-title":"Graphs and Combinatorics"},{"key":"2838_CR3","doi-asserted-by":"crossref","unstructured":"Chebotarev, P.l., Peleg, D.: The power of small coalitions under two-tier majority on regular graphs. Discrete Appl. Math. 340, 239\u2013258 (2023)","DOI":"10.1016\/j.dam.2023.07.011"},{"issue":"2","key":"2838_CR4","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0012-365X(86)90088-9","volume":"61","author":"PC Fishburn","year":"1986","unstructured":"Fishburn, P.C., Hwang, F.K., Lee, H.: Do local majorities force a global majority? Discrete. Math. 61(2), 165\u2013179 (1986)","journal-title":"Discrete. Math."},{"key":"2838_CR5","doi-asserted-by":"crossref","unstructured":"Lerman, K., Yan, X., Wu, X.: The \u201cmajority illusion\u201d in social networks. PLoS ONE 11(2), 0147617 (2016)","DOI":"10.1371\/journal.pone.0147617"},{"issue":"1","key":"2838_CR6","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0012-365X(94)00160-3","volume":"146","author":"P Lison\u00eak","year":"1995","unstructured":"Lison\u00eak, P.: Local and global majorities revisited. Discret. Math. 146(1), 153\u2013158 (1995)","journal-title":"Discret. Math."},{"key":"2838_CR7","doi-asserted-by":"crossref","unstructured":"F\u00fcredi, Z., Simonovits, M.: The History of Degenerate (Bipartite) Extremal Graph Problems. In: Erd\u0151s Centennial, pp. 169\u2013264. Springer, Berlin (2013)","DOI":"10.1007\/978-3-642-39286-3_7"},{"key":"2838_CR8","first-page":"436","volume":"48","author":"P Tur\u00e1n","year":"1941","unstructured":"Tur\u00e1n, P.: On an external problem in graph theory. Mat. Fiz. Lapok 48, 436\u2013452 (1941)","journal-title":"Mat. Fiz. Lapok"},{"issue":"3","key":"2838_CR9","doi-asserted-by":"publisher","first-page":"19","DOI":"10.4064\/cm-3-1-19-30","volume":"1","author":"P Tur\u00e1n","year":"1954","unstructured":"Tur\u00e1n, P.: On the theory of graphs. In Colloquium Mathematicum 1(3), 19\u201330 (1954)","journal-title":"In Colloquium Mathematicum"},{"key":"2838_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":"3","key":"2838_CR11","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/0095-8956(80)90085-4","volume":"29","author":"A Blass","year":"1980","unstructured":"Blass, A., Harary, F., Miller, Z.: Which trees are link graphs? J. Combin. Theory Ser. B 29(3), 277\u2013292 (1980)","journal-title":"J. Combin. Theory Ser. B"},{"key":"2838_CR12","unstructured":"Conder, M., Schillewaert, J., Verret, G.: Parameters for certain locally-regular graphs. arXiv preprint arXiv:2112.00276 (2021)"},{"issue":"3","key":"2838_CR13","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1002\/jgt.3190090313","volume":"9","author":"JI Hall","year":"1985","unstructured":"Hall, J.I.: Graphs with constant link and small degree or order. J. Graph Theory 9(3), 419\u2013444 (1985). https:\/\/doi.org\/10.1002\/jgt.3190090313","journal-title":"J. Graph Theory"},{"key":"2838_CR14","first-page":"385","volume":"102","author":"F Larri\u00f3n","year":"2011","unstructured":"Larri\u00f3n, F., Piza\u00f1a, M.A., Villarroel-Flores, R.: Small locally $$nk_2$$ graphs. ARS Comb. 102, 385\u2013391 (2011)","journal-title":"ARS Comb."},{"issue":"2","key":"2838_CR15","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/0022-314X(89)90006-1","volume":"33","author":"B Reznick","year":"1989","unstructured":"Reznick, B.: The sum of the squares of the parts of a partition, and some related questions. J. Number Theory 33(2), 199\u2013208 (1989)","journal-title":"J. Number Theory"},{"key":"2838_CR16","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/j.dam.2022.09.019","volume":"324","author":"Y Caro","year":"2023","unstructured":"Caro, Y., Lauri, J., Zarb, C.: The feasibility problem for line graphs. Discret. Appl. Math. 324, 167\u2013180 (2023). https:\/\/doi.org\/10.1016\/j.dam.2022.09.019","journal-title":"Discret. Appl. Math."},{"issue":"4","key":"2838_CR17","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1007\/s00493-014-2897-6","volume":"34","author":"X Dahan","year":"2014","unstructured":"Dahan, X.: Regular graphs of large girth and arbitrary degree. Combinatorica 34(4), 407\u2013426 (2014). https:\/\/doi.org\/10.1007\/s00493-014-2897-6","journal-title":"Combinatorica"},{"key":"2838_CR18","unstructured":"Exoo, G., Jajcay, R.: Dynamic cage survey. Electron. J. Combin. DS16, 48 (2008)"},{"issue":"1","key":"2838_CR19","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/0166-218X(94)00058-L","volume":"60","author":"F Lazebnik","year":"1995","unstructured":"Lazebnik, F., Ustimenko, V.A.: Explicit construction of graphs with an arbitrary large girth and of large size. Discret. Appl. Math. 60(1), 275\u2013284 (1995). https:\/\/doi.org\/10.1016\/0166-218X(94)00058-L","journal-title":"Discret. Appl. Math."},{"key":"2838_CR20","unstructured":"Catlin, P.: Embedding subgraphs under extremal degree conditions. PhD thesis (1976)"},{"issue":"3","key":"2838_CR21","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/0095-8956(78)90005-9","volume":"25","author":"N Sauer","year":"1978","unstructured":"Sauer, N., Spencer, J.: Edge disjoint placement of graphs. J. Combin. Theory Ser. B 25(3), 295\u2013302 (1978). https:\/\/doi.org\/10.1016\/0095-8956(78)90005-9","journal-title":"J. Combin. Theory Ser. B"}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-024-02838-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-024-02838-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-024-02838-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,18]],"date-time":"2025-01-18T13:32:04Z","timestamp":1737207124000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-024-02838-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,8]]},"references-count":21,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["2838"],"URL":"https:\/\/doi.org\/10.1007\/s00373-024-02838-w","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"type":"print","value":"0911-0119"},{"type":"electronic","value":"1435-5914"}],"subject":[],"published":{"date-parts":[[2024,10,8]]},"assertion":[{"value":"31 January 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 September 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 September 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 October 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":"106"}}