{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T17:59:54Z","timestamp":1773856794576,"version":"3.50.1"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2017,10,20]],"date-time":"2017-10-20T00:00:00Z","timestamp":1508457600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["11626234"],"award-info":[{"award-number":["11626234"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Key Project of Hubei Provincial Natural Science Foundation","award":["2015CFA144"],"award-info":[{"award-number":["2015CFA144"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Soft Comput"],"published-print":{"date-parts":[[2019,2]]},"DOI":"10.1007\/s00500-017-2861-7","type":"journal-article","created":{"date-parts":[[2017,10,19]],"date-time":"2017-10-19T22:17:43Z","timestamp":1508451463000},"page":"1337-1346","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Uncertain vertex coloring problem"],"prefix":"10.1007","volume":"23","author":[{"given":"Lin","family":"Chen","sequence":"first","affiliation":[]},{"given":"Jin","family":"Peng","sequence":"additional","affiliation":[]},{"given":"Dan A.","family":"Ralescu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,10,20]]},"reference":[{"issue":"5","key":"2861_CR1","doi-asserted-by":"publisher","first-page":"711","DOI":"10.1090\/S0002-9904-1976-14122-5","volume":"82","author":"K Appel","year":"1976","unstructured":"Appel K, Haken W (1976) Every planar map is four colorable. Bull Am Math Soc 82(5):711\u2013712","journal-title":"Bull Am Math Soc"},{"issue":"1","key":"2861_CR2","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/BF02122551","volume":"8","author":"B Bollob\u00e1s","year":"1988","unstructured":"Bollob\u00e1s B (1988) The chromatic number of random graphs. Combinatorica 8(1):49\u201355","journal-title":"Combinatorica"},{"issue":"6","key":"2861_CR3","doi-asserted-by":"publisher","first-page":"1859","DOI":"10.1016\/j.cor.2008.05.012","volume":"36","author":"F Carrabs","year":"2009","unstructured":"Carrabs F, Cerulli R, Gentili M (2009) The labeled maximum matching problem. Comput Oper Res 36(6):1859\u20131871","journal-title":"Comput Oper Res"},{"issue":"1","key":"2861_CR4","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1016\/j.ejor.2012.01.046","volume":"220","author":"R Cerulli","year":"2012","unstructured":"Cerulli R, Donato R, Raiconi A (2012) Exact and heuristic methods to maximize network lifetime in wireless sensor networks with adjustable sensing ranges. Eur J Oper Res 220(1):58\u201366","journal-title":"Eur J Oper Res"},{"issue":"4","key":"2861_CR5","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1145\/88616.88621","volume":"12","author":"F Chow","year":"1990","unstructured":"Chow F, Hennessy J (1990) The priority-based coloring approach to register allocation. ACM Trans Program Lang Syst 12(4):501\u2013536","journal-title":"ACM Trans Program Lang Syst"},{"key":"2861_CR6","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/j.dam.2015.10.005","volume":"204","author":"M Demange","year":"2016","unstructured":"Demange M, Ekim T, Ries B (2016) On the minimum and maximum selective graph coloring problems in some graph classes. Discret Appl Math 204:77\u201389","journal-title":"Discret Appl Math"},{"issue":"5","key":"2861_CR7","doi-asserted-by":"publisher","first-page":"893","DOI":"10.1016\/j.ejc.2011.09.016","volume":"33","author":"F Eisenbrand","year":"2012","unstructured":"Eisenbrand F, Niemeier M (2012) Coloring fuzzy circular interval graphs. Eur J Comb 33(5):893\u2013904","journal-title":"Eur J Comb"},{"key":"2861_CR8","first-page":"290","volume":"6","author":"P Erd\u0151s","year":"1959","unstructured":"Erd\u0151s P, R\u00e9nyi A (1959) On random graph. Publ Math 6:290\u2013297","journal-title":"On random graph. Publ Math"},{"issue":"6","key":"2861_CR9","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1145\/367766.368168","volume":"5","author":"R Floyd","year":"1962","unstructured":"Floyd R (1962) Algorithm 97: shortest path. Commun ACM 5(6):345","journal-title":"Commun ACM"},{"issue":"1","key":"2861_CR10","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1002\/net.21716","volume":"69","author":"F Furini","year":"2017","unstructured":"Furini F, Gabrel V, Ternier I (2017) An improved DSATUR-based branch-and-bound algorithm for the vertex coloring problem. Networks 69(1):124\u2013141","journal-title":"Networks"},{"issue":"4","key":"2861_CR11","doi-asserted-by":"publisher","first-page":"1449","DOI":"10.1007\/s00500-015-1597-5","volume":"20","author":"X Gao","year":"2016","unstructured":"Gao X (2016) Tree index of uncertain graphs. Soft Comput 20(4):1449\u20131458","journal-title":"Soft Comput"},{"issue":"1","key":"2861_CR12","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1142\/S0218488513500074","volume":"21","author":"X Gao","year":"2013","unstructured":"Gao X, Gao Y (2013) Connectedness index of uncertain graph. Int J Uncertain Fuzziness Knowl Based Syst 21(1):127\u2013137","journal-title":"Int J Uncertain Fuzziness Knowl Based Syst"},{"issue":"4","key":"2861_CR13","doi-asserted-by":"publisher","first-page":"981","DOI":"10.1109\/TFUZZ.2015.2500267","volume":"24","author":"Y Gao","year":"2016","unstructured":"Gao Y, Qin Z (2016) On computing the edge-connectivity of an uncertain graph. IEEE Trans Fuzzy Syst 24(4):981\u2013991","journal-title":"IEEE Trans Fuzzy Syst"},{"key":"2861_CR14","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/j.ins.2014.10.048","volume":"296","author":"Y Gao","year":"2015","unstructured":"Gao Y, Yang L, Li S, Kar S (2015) On distribution function of the diameter in uncertain graph. Inf Sci 296:61\u201374","journal-title":"Inf Sci"},{"issue":"4","key":"2861_CR15","doi-asserted-by":"publisher","first-page":"1141","DOI":"10.1214\/aoms\/1177706098","volume":"30","author":"E Gilbert","year":"1959","unstructured":"Gilbert E (1959) Random graphs. Ann Math Stat 30(4):1141\u20131144","journal-title":"Ann Math Stat"},{"issue":"24","key":"2861_CR16","doi-asserted-by":"publisher","first-page":"3645","DOI":"10.1016\/j.ins.2006.01.006","volume":"176","author":"D G\u00f3mez","year":"2006","unstructured":"G\u00f3mez D, Montero J, Y\u00e1\u00f1ez J (2006) A coloring fuzzy graph approach for image classification. Inf Sci 176(24):3645\u20133657","journal-title":"Inf Sci"},{"key":"2861_CR17","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1016\/j.cor.2013.09.019","volume":"43","author":"Y Jin","year":"2014","unstructured":"Jin Y, Hao J, Hamiez J (2014) A memetic algorithm for the minimum sum coloring problem. Comput Oper Res 43:318\u2013327","journal-title":"Comput Oper Res"},{"issue":"2","key":"2861_CR18","doi-asserted-by":"publisher","first-page":"883","DOI":"10.3233\/IFS-151810","volume":"30","author":"E Keshavarz","year":"2016","unstructured":"Keshavarz E (2016) Vertex-coloring of fuzzy graphs: a new approach. J Intell Fuzzy Syst 30(2):883\u2013893","journal-title":"J Intell Fuzzy Syst"},{"key":"2861_CR19","volume-title":"Uncertainty theory","author":"B Liu","year":"2007","unstructured":"Liu B (2007) Uncertainty theory, 2nd edn. Springer, Berlin","edition":"2"},{"issue":"1","key":"2861_CR20","first-page":"3","volume":"3","author":"B Liu","year":"2009","unstructured":"Liu B (2009) Some research problems in uncertainty theory. J Uncertain Syst 3(1):3\u201310","journal-title":"J Uncertain Syst"},{"issue":"1","key":"2861_CR21","first-page":"3","volume":"6","author":"B Liu","year":"2012","unstructured":"Liu B (2012) Why is there a need for uncertainty theory. J Uncertain Syst 6(1):3\u201310","journal-title":"J Uncertain Syst"},{"issue":"1","key":"2861_CR22","first-page":"3","volume":"8","author":"B Liu","year":"2014","unstructured":"Liu B (2014) Uncertain random graph and uncertain random network. J Uncertain Syst 8(1):3\u201312","journal-title":"J Uncertain Syst"},{"issue":"11","key":"2861_CR23","doi-asserted-by":"publisher","first-page":"4363","DOI":"10.1007\/s00500-015-1992-y","volume":"20","author":"Y Liu","year":"2016","unstructured":"Liu Y, Liu J, Wang K, Zhang H (2016) A theoretical extension on the operational law for monotone functions of uncertain variables. Soft Comput 20(11):4363\u20134376","journal-title":"Soft Comput"},{"issue":"1","key":"2861_CR24","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/j.ejor.2009.07.016","volume":"203","author":"Z L\u00fc","year":"2010","unstructured":"L\u00fc Z, Hao J (2010) A memetic algorithm for graph coloring. Eur J Oper Res 203(1):241\u2013250","journal-title":"Eur J Oper Res"},{"issue":"2","key":"2861_CR25","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1287\/ijoc.1070.0245","volume":"20","author":"E Malaguti","year":"2008","unstructured":"Malaguti E, Monaci M, Toth P (2008) A metaheuristic approach for the vertex coloring problem. Inf J Comput 20(2):302\u2013316","journal-title":"Inf J Comput"},{"issue":"1","key":"2861_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1111\/j.1475-3995.2009.00696.x","volume":"17","author":"E Malaguti","year":"2010","unstructured":"Malaguti E, Toth P (2010) A survey on vertex coloring problems. Int Trans Oper Res 17(1):1\u201334","journal-title":"Int Trans Oper Res"},{"issue":"8","key":"2861_CR27","doi-asserted-by":"publisher","first-page":"1287","DOI":"10.1016\/j.jcss.2013.06.003","volume":"79","author":"Z Mann","year":"2013","unstructured":"Mann Z, Szajk\u00f3 A (2013) Average-case complexity of backtrack search for coloring sparse random graphs. J Comput Syst Sci 79(8):1287\u20131301","journal-title":"J Comput Syst Sci"},{"issue":"1","key":"2861_CR28","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1287\/ijoc.2015.0667","volume":"28","author":"D Morrison","year":"2016","unstructured":"Morrison D, Sewell E, Jacobson S (2016) Solving the pricing problem in a branch-and-price algorithm for graph coloring using zero-suppressed binary decision diagrams. Inf J Comput 28(1):67\u201382","journal-title":"Inf J Comput"},{"issue":"3","key":"2861_CR29","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/j.omega.2004.04.006","volume":"33","author":"S Mu\u00f1oz","year":"2005","unstructured":"Mu\u00f1oz S, Ortu\u00f1o M, Ram\u00edrez J, Y\u00e1\u00f1ez J (2005) Coloring fuzzy graphs. Omega 33(3):211\u2013221","journal-title":"Omega"},{"issue":"13","key":"2861_CR30","doi-asserted-by":"publisher","first-page":"3723","DOI":"10.1007\/s00500-015-2026-5","volume":"21","author":"T Pramanik","year":"2017","unstructured":"Pramanik T, Samanta S, Sarkar B, Pal M (2017) Fuzzy \n                    \n                      \n                    \n                    $$\\phi $$\n                    \n                      \n                        \u03d5\n                      \n                    \n                  -tolerance competition graphs. Soft Comput 21(13):3723\u20133734","journal-title":"Soft Comput"},{"issue":"1","key":"2861_CR31","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1006\/jctb.1997.1750","volume":"70","author":"N Robertson","year":"1997","unstructured":"Robertson N, Sanders D, Seymour P, Thomas R (1997) The four-colour theorem. J Comb Theory Ser B 70(1):2\u201344","journal-title":"J Comb Theory Ser B"},{"key":"2861_CR32","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/B978-0-12-775260-0.50008-6","volume-title":"Fuzzy sets and their applications to cognitive and decision processes","author":"A Rosenfeld","year":"1975","unstructured":"Rosenfeld A (1975) Fuzzy graphs. In: Zadeh L, Fu K, Shimura M (eds) Fuzzy sets and their applications to cognitive and decision processes. Academic Press, New York, pp 77\u201395"},{"issue":"5","key":"2861_CR33","doi-asserted-by":"publisher","first-page":"2331","DOI":"10.3233\/IFS-141521","volume":"28","author":"I Rosyida","year":"2015","unstructured":"Rosyida I, Widodo Indrati C, Sugeng K (2015) A new approach in determining fuzzy chromatic number of a fuzzy graph. J Intell Fuzzy Syst 28(5):2331\u20132341","journal-title":"J Intell Fuzzy Syst"},{"key":"2861_CR34","doi-asserted-by":"crossref","unstructured":"Rosyida I, Widodo, Indrati C, Sugeng K (2016a) An \n                    \n                      \n                    \n                    $$\\alpha $$\n                    \n                      \n                        \u03b1\n                      \n                    \n                  -cut chromatic number of a total uncertain graph and its properties. In: Proceedings of the 7th SEAMS UGM international conference on mathematics and its applications 2015, pp 1\u20138","DOI":"10.1063\/1.4940819"},{"key":"2861_CR35","doi-asserted-by":"publisher","unstructured":"Rosyida I, Peng J, Chen L, Widodo, Indrati C, Sugeng K (2016b) An uncertain chromatic number of an uncertain graph based on \n                    \n                      \n                    \n                    $$\\alpha $$\n                    \n                      \n                        \u03b1\n                      \n                    \n                  -cut coloring. Fuzzy Optim Decis Making. doi:\n                    10.1007\/s10700-016-9260-x","DOI":"10.1007\/s10700-016-9260-x"},{"issue":"1","key":"2861_CR36","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/s13370-015-0317-8","volume":"27","author":"S Samanta","year":"2016","unstructured":"Samanta S, Pramanik T, Pal M (2016) Fuzzy colouring of fuzzy graphs. Afr Math 27(1):37\u201350","journal-title":"Afr Math"},{"issue":"10","key":"2861_CR37","doi-asserted-by":"publisher","first-page":"3381","DOI":"10.1016\/j.disc.2008.09.038","volume":"309","author":"C Sommer","year":"2009","unstructured":"Sommer C (2009) A note on coloring sparse random graphs. Discret Math 309(10):3381\u20133384","journal-title":"Discret Math"},{"issue":"3","key":"2861_CR38","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1016\/S0019-9958(65)90241-X","volume":"8","author":"L Zadeh","year":"1965","unstructured":"Zadeh L (1965) Fuzzy sets. Inf Control 8(3):338\u2013353","journal-title":"Inf Control"},{"issue":"20","key":"2861_CR39","first-page":"10279","volume":"218","author":"B Zhang","year":"2012","unstructured":"Zhang B, Peng J (2012) Euler index in uncertain graph. Appl Math Comput 218(20):10279\u201310288","journal-title":"Appl Math Comput"},{"issue":"3","key":"2861_CR40","first-page":"381","volume":"12","author":"B Zhang","year":"2013","unstructured":"Zhang B, Peng J (2013) Matching index of uncertain graph: concept and algorithm. Appl Comput Math 12(3):381\u2013391","journal-title":"Appl Comput Math"}],"container-title":["Soft Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00500-017-2861-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00500-017-2861-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00500-017-2861-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,12,23]],"date-time":"2019-12-23T03:42:13Z","timestamp":1577072533000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00500-017-2861-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,10,20]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,2]]}},"alternative-id":["2861"],"URL":"https:\/\/doi.org\/10.1007\/s00500-017-2861-7","relation":{},"ISSN":["1432-7643","1433-7479"],"issn-type":[{"value":"1432-7643","type":"print"},{"value":"1433-7479","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,10,20]]},"assertion":[{"value":"20 October 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Compliance with ethical standards"}},{"value":"The authors declare that there is no conflict of interests regarding the publication of this paper.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"This article does not contain any studies with human participants or animals performed by any of the authors.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}},{"value":"Informed consent was obtained from all individual participants included in the study.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Informed consent"}}]}}