{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,25]],"date-time":"2026-09-25T07:38:31Z","timestamp":1790321911965,"version":"4.1.0"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642321467","type":"print"},{"value":"9783642321474","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-32147-4_29","type":"book-chapter","created":{"date-parts":[[2012,7,5]],"date-time":"2012-07-05T11:54:50Z","timestamp":1341489290000},"page":"320-331","source":"Crossref","is-referenced-by-count":4,"title":["Selective Graph Coloring in Some Special Classes of Graphs"],"prefix":"10.1007","author":[{"given":"Marc","family":"Demange","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"J\u00e9r\u00f4me","family":"Monnot","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Petrica","family":"Pop","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bernard","family":"Ries","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"29_CR1","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice Hall (1993)"},{"key":"29_CR2","doi-asserted-by":"crossref","unstructured":"Al-Mouhamed, M., Dandashi, A.: Graph Coloring for class scheduling. In: IEEE\/ACS Internation Conference on Computer Systems and Applications (AICCSA), pp. 1\u20134 (2010)","DOI":"10.1109\/AICCSA.2010.5586963"},{"key":"29_CR3","volume-title":"Graphes et hypergraphes","author":"C. Berge","year":"1970","unstructured":"Berge, C.: Graphes et hypergraphes. Dunod, Paris (1970)"},{"key":"29_CR4","doi-asserted-by":"publisher","first-page":"1129","DOI":"10.1016\/j.endm.2010.05.143","volume":"36","author":"Y. Chung","year":"2010","unstructured":"Chung, Y., Demange, M.: On inverse chromatic number problems. Electronic Notes in Discrete Mathematics\u00a036, 1129\u20131136 (2010)","journal-title":"Electronic Notes in Discrete Mathematics"},{"key":"29_CR5","unstructured":"Berman, P., Karpinski, M., Scott, A.D.: Approximation Hardness of Short Symmetric Instances of MAX-3SAT. Electronic Colloquium on Computational Complexity. Technical Report TR03-049 (2003)"},{"issue":"3","key":"29_CR6","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V. Chvat\u00e1l","year":"1979","unstructured":"Chvat\u00e1l, V.: A Greedy Heuristic for the Set-Covering Problem. Mathematics of Operations Research\u00a04(3), 233\u2013235 (1979)","journal-title":"Mathematics of Operations Research"},{"key":"29_CR7","doi-asserted-by":"publisher","first-page":"864","DOI":"10.1137\/S0097539792225297","volume":"23","author":"E. Dahlhaus","year":"1994","unstructured":"Dahlhaus, E., Seymour, P.D., Papadimitriou, C.H., Yannakakis, M.: The complexity of multiterminal cuts. SIAM J. Computing\u00a023, 864\u2013894 (1994)","journal-title":"SIAM J. Computing"},{"key":"29_CR8","first-page":"289","volume":"2","author":"A. Dolgui","year":"2001","unstructured":"Dolgui, A., Sotskov, Y.N., Werner, F.: Mixed graph coloring via unit-time job-shop. Internat. J. Math. Algorithms\u00a02, 289\u2013323 (2001)","journal-title":"Internat. J. Math. Algorithms"},{"issue":"4","key":"29_CR9","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. Journal of the ACM\u00a045(4), 634\u2013652 (1998)","journal-title":"Journal of the ACM"},{"issue":"1","key":"29_CR10","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.tcs.2008.09.065","volume":"410","author":"M. Fellows","year":"2009","unstructured":"Fellows, M., Hermelin, D., Rosamond, F.A., Vialette, S.: On the parametrized complexity of multiple-interval graph problems. Theoretical Computer Science\u00a0410(1), 53\u201361 (2009)","journal-title":"Theoretical Computer Science"},{"key":"29_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0377-2217(02)00404-6","volume":"148","author":"C. Feremans","year":"2003","unstructured":"Feremans, C., Labbe, M., Laporte, G.: Generalized network design problems. European Journal of Operations Research\u00a0148, 1\u201313 (2003)","journal-title":"European Journal of Operations Research"},{"key":"29_CR12","doi-asserted-by":"publisher","first-page":"2384","DOI":"10.1016\/j.cor.2005.09.010","volume":"34","author":"M. Gamache","year":"2007","unstructured":"Gamache, M., Hertz, A., Ouellet, J.: A graph coloring model for a feasibility problem in crew scheduling. Computers and Operations Research\u00a034, 2384\u20132395 (2007)","journal-title":"Computers and Operations Research"},{"key":"29_CR13","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability, a guide to the theory of $\\mathcal{NP}$ -completeness. Freeman, New York (1979)"},{"key":"29_CR14","doi-asserted-by":"crossref","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified $\\mathcal{NP}$ -complete problems. In: Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, pp. 47\u201363 (1974)","DOI":"10.1145\/800119.803884"},{"issue":"17","key":"29_CR15","doi-asserted-by":"publisher","first-page":"3625","DOI":"10.1016\/j.dam.2009.02.024","volume":"157","author":"K. Giaro","year":"2009","unstructured":"Giaro, K., Kubale, M., Obszarski, P.: A graph coloring approach to scheduling of multiprocessor tasks on dedicated machines with availability constraints. Discrete Applied Mathematics\u00a0157(17), 3625\u20133630 (2009)","journal-title":"Discrete Applied Mathematics"},{"key":"29_CR16","unstructured":"Korte, B., Vygen, J.: Combinatorial Optimization, Theory and Algorithms, 4th edn. Springer (2008)"},{"key":"29_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/978-3-642-25870-1_17","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"A.R.A. McGrae","year":"2011","unstructured":"McGrae, A.R.A., Zito, M.: Empires Make Cartography Hard: The Complexity of the Empire Colouring Problem. In: Kolman, P., Kratochv\u00edl, J. (eds.) WG 2011. LNCS, vol.\u00a06986, pp. 179\u2013190. Springer, Heidelberg (2011)"},{"key":"29_CR18","doi-asserted-by":"publisher","first-page":"592","DOI":"10.1016\/j.dam.2009.10.016","volume":"158","author":"B. Ries","year":"2010","unstructured":"Ries, B.: Complexity of two coloring problems in cubic planar bipartite mixed graphs. Discrete Applied Mathematics\u00a0158, 592\u2013596 (2010)","journal-title":"Discrete Applied Mathematics"},{"key":"29_CR19","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/s00037-005-0200-3","volume":"14","author":"S. Safra","year":"2005","unstructured":"Safra, S., Schwartz, O.: On the complexity of approximating TSP with neighborhoods and related problems. Computational Complexity\u00a014, 281\u2013307 (2005)","journal-title":"Computational Complexity"},{"key":"29_CR20","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1080\/0233193021000004994","volume":"51","author":"Y.N. Sotskov","year":"2002","unstructured":"Sotskov, Y.N., Tanaev, V.S., Werner, F.: Scheduling problems and mixed graph colorings. Optimization\u00a051, 597\u2013624 (2002)","journal-title":"Optimization"},{"key":"29_CR21","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0166-218X(84)90081-7","volume":"8","author":"C.A. Tovey","year":"1984","unstructured":"Tovey, C.A.: A simplified $\\mathcal{NP}$ -complete satisfiability problem. Discrete Applied Mathematics\u00a08, 85\u201389 (1984)","journal-title":"Discrete Applied Mathematics"},{"key":"29_CR22","unstructured":"West, D.B.: Introduction to Graph Theory, 2nd edn. Prentice Hall (2001)"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-32147-4_29.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,3]],"date-time":"2025-04-03T07:20:13Z","timestamp":1743664813000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-32147-4_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642321467","9783642321474"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-32147-4_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}