Recognition of split-graphic sequences

[1] S. M. de Almeida, C. P. de Mello, A. Morgana, Classification problem for split graphs, J. Brazilian Comp. Soc., 18, (2) (2012) 95-101. ⇒266Search in Google Scholar

[2] M. D. Barrus, Hereditary unigraphs and Erdős-Gallai equalities, Discrete Math., 313, (21) (2013) 2469-2481. ⇒263Search in Google Scholar

[3] D. Bauer, S. L. Hakimi, E. Schmeichel, Recognising of tough graphs is NP-hard, Discrete Appl. Math., 28 (1995) 191-195. ⇒266Search in Google Scholar

[4] C. Benzaken, P. L. Hammer, D. De Werra, Split graphs of Dilworth number 2, Discrete Math., 55, (2) (1985) 123-127. ⇒256Search in Google Scholar

[5] Z. Blázsik, M. Hujter, A. Pluhár, Zs. Tuza, Graphs with no induced C4 and 2K2, Discrete Math., 115 (1993) 51-55. ⇒256, 263Search in Google Scholar

[6] E. Boros, V. A. Gurvich, I. Zverovich, On split and almost CIS-graphs, Australas. J. Combin., 43 (2009) 163-180. ⇒255Search in Google Scholar

[7] A. Brandst¨adt, Partitions of graphs into one or two stable sets and cliques, Discrete Math., 152 (1996) 47-54. ⇒254, 256Search in Google Scholar

[8] A. Brandst¨adt, Corrigendum, Discrete Math., 186 (1998) 295-295. ⇒254, 256Search in Google Scholar

[9] A. Brandst¨adt, P. L. Hammer, V. B. Le, V. V. Lozin, Bisplit graphs, Discrete Mathematics 299 (2005) 11-32. ⇒255, 25610.1016/j.disc.2004.08.046Search in Google Scholar

[10] A. Brandst¨adt, V. B. Le, J. P. Spinrad, Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, SIAM, Philadelphia, PL, 1999. ⇒254, 256, 266Search in Google Scholar

[11] R. E. Burkard, P. L. Hammer, A note on Hamiltonian split graphs, J. Comb. Graph Theory, Series B, 28 (1980) 245-248. ⇒26510.1016/0095-8956(80)90069-6Search in Google Scholar

[12] G. Chartrand, L. Lesniak, P. Zhang, Graphs and Digraphs, CRC Press, Boca Raton, FL, 2011. ⇒25310.1201/b14892Search in Google Scholar

[13] V. Chungphaisan, Conditions for a sequences to be r-graphic, Discrete Math., 7 (1974) 31-39. ⇒257, 25810.1016/S0012-365X(74)80016-6Search in Google Scholar

[14] V. Chvátal, The toughness of graphs, Discrete Math., 5 (1973) 215-228. ⇒26610.1016/0012-365X(73)90138-6Search in Google Scholar

[15] R. J. Clarke, Covering a set by subsets, Discrete Math., 181 (1990) 147-152. ⇒ 26410.1016/0012-365X(90)90146-9Search in Google Scholar

[16] T. H. Cormen, Ch. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms Third edition, The MIT Press/McGraw Hill, Cambridge/New York, 2009. ⇒275Search in Google Scholar

[17] P. Erdős, T. Gallai, Gráfok előírt fok´u pontokkal (Graphs with given degrees of vertices), Mat. Lapok, 11 (1960), 264-274. ⇒253, 256, 258, 280Search in Google Scholar

[18] P. Erdős, A. Gyárfás, Split and balanced colorings of complete graphs, Discrete Mathematics, 200, (1-3) (1999), 79-86. ⇒264Search in Google Scholar

[19] P. Erdős, M. S. Jacobson, J. Lehel, Graphs realizing the same degree sequences and their respective clique numbers, in: Y. Alavi (Ed.), Graph Theory, Combinatorics and Applications, vol. 1, John Wiley and Sons, New York, 1991, 439-449. ⇒264Search in Google Scholar

[20] T. Feder, P. Hell, S. Klein, R. Motwani, List partitions, SIAM J. Discrete Math, 16 (2003) 449-478. ⇒278Search in Google Scholar

[21] S. Földes, P. Hammer, Split graphs having Dilworth number two, Canad. J. Math. 29, (3) (1977) 666-672. ⇒254, 25610.4153/CJM-1977-069-1Search in Google Scholar

[22] S. Földes, P. Hammer, Split graphs, in (ed. E. Hoffman et al.) Proc. 8th South- Eastern Conf. Combinatorics, Graph Theory Comp. Congressus Num., XIX (1977) 311-315. ⇒254, 256, 263Search in Google Scholar

[23] S. Földes, P. Hammer, The Dilworth number of a graph, Annals Discrete Math., 2 (1978) 211-219. ⇒25610.1016/S0167-5060(08)70334-0Search in Google Scholar

[24] D. R. Fulkerson, A. J. Hoffman, M. H. McAndrew, Some properties of graphs with multiple edges, Canad. J. Math., 17 (1965) 166-177. ⇒253, 269, 27110.4153/CJM-1965-016-2Search in Google Scholar

[25] V. Gasharov, The Erdős-Gallai criterion and symmetric functions, Europ. J. Combinatorics, 18 (1997) 287-294. ⇒25810.1006/eujc.1996.0096Search in Google Scholar

[26] M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, 1980. ⇒254, 256, 263, 27810.1016/B978-0-12-289260-8.50019-4Search in Google Scholar

[27] R. J. Gould, M. S. Jacobson, J. Lehel, Potentially G-graphical degree sequences, in: Y. Alavi (Ed.), Combinatorics, Graph Theory and Algorithms, vol. 1, New Issues Press, Kalamazoo, Michigan, 1999, 451-460. ⇒261, 264Search in Google Scholar

[28] J. L. Gross, J. Yellen, P. Zhang. Handbook of Graph Theory, CRC Press, Boca Raton, FL, 2013. ⇒252, 253, 254, 25610.1201/b16132Search in Google Scholar

[29] A. Gyárfás, J. Lehel, On-line and first fit colorings of graphs. J. Graph Theory, 12, (2) (1988) 217-227. ⇒264Search in Google Scholar

[30] A. Gyárfás, Generalized split graphs and Ramsey numbers, J. Comb. Theory, Series A 81, (2) (1998) 255-261. ⇒255, 256 Search in Google Scholar

[31] M. Habib, A.Mamcarz, Colored modular and split decompositions of graphs with applications to trigraphs, in (ed. D. Kratsch and I. Todinca) Graph-Theoretic Concepts in Computer Science (40th International Workshop, WG 2014, Nouanle- Fuzelier, France, June 25-27, 2014). Series: Lecture Notes in Computer Science, 8747, Springer Verlag, Berlin, 2014, 263-274. ⇒26610.1007/978-3-319-12340-0_22Search in Google Scholar

[32] S. L. Hakimi, On the realizability of a set of integers as degrees of the vertices of a simple graph. J. SIAM Appl. Math., 10 (1962), 496-506. ⇒257, 25810.1137/0110037Search in Google Scholar

[33] S. L. Hakimi, E. F. Schmeichel, Graphs and their degree sequences: A survey, in: Theory and Applications of Graphs, Lecture Notes in Math. 642, Springer- Verlag, Berlin 1978, 225-235. ⇒26110.1007/BFb0070380Search in Google Scholar

[34] P. L. Hammer, B. Simeone, The splittance of a graph, Combinatorica, 1, (3) (1981) 275-284. ⇒263, 264, 27810.1007/BF02579333Search in Google Scholar

[35] P. Hanion, Enumeration of graphs by degree sequence, J. Graph Theory, 3 (1979) 295-299. ⇒26010.1002/jgt.3190030313Search in Google Scholar

[36] V. Havel, A remark on the existence of finite graphs (Czech), ˘ Casopis P˘est. Mat., 80 (1955), 477-480. ⇒257, 258Search in Google Scholar

[37] P. Heggerness, D. Kratsch, Linear-time certifying algorithms for recognizing split graphs and related graph classes, Nordic J. Comp., 14 (2007) 87-108. ⇒278Search in Google Scholar

[38] P. Heggernes, F. Mancini, Minimal split completions. Discrete Appl. Math., 157, (12) (2009) 2659-2669. ⇒266Search in Google Scholar

[39] A. P. Heinz, Total number of split graphs (chordal + chordal complement) on n vertices. In: (ed. N. J. A. Sloane): The On-Line Encyclopedia of the Integer Sequences. 2014. ⇒265Search in Google Scholar

[40] P. Hell, D. Kirkpatrick, Linear-time certifying algorithms for near-graphical sequences, Discrete Math., 309, (18) (2009) 5703-5713. ⇒260Search in Google Scholar

[41] P. Hell, S. Klein, F. Protti, L. Tito, On generalized split graphs, Electronic Notes Disc. Math., 7 (2001) 98-101. ⇒25510.1016/S1571-0653(04)00234-3Search in Google Scholar

[42] L. Ibarra, Fully dynamic algorithms for chordal graphs and split graphs, ACM Trans. Algorithms, 4(4), (2008), Art. 40, 20 pages. ⇒26610.1145/1383369.1383371Search in Google Scholar

[43] A. Iványi, Reconstruction of complete interval tournaments, Acta Univ. Sapientiae, Inform., 1, (1) (2009) 71-88. ⇒252, 253, 256Search in Google Scholar

[44] A. Iványi, Reconstruction of complete interval tournaments II, Acta Univ. Sapientiae, Math., 2, (1) (2010) 47-71. ⇒252, 253Search in Google Scholar

[45] A. Iványi, Degree sequences of multigraphs, Annales Univ. Sci. Budapest., Rolando Eötvös Nom., Sectio Comp., 37 (2012) 195-214. ⇒ 256, 259, 260, 262Search in Google Scholar

[46] A. Iványi, Z. Kása, Parallel enumeration of graphical sequences (in Hungarian), Alk. Mat. Lapok, 31, (2014) 1-58. ⇒260Search in Google Scholar

[47] A. Iványi, L. Lucz, Degree sequences of multigraphs (in Hungarian), Alk. Mat. Lapok, 29, (2012) 1-54. ⇒260Search in Google Scholar

[48] A. Iványi, L. Lucz, T. F. M´ori, P. S´ot´er, On the Erdős-Gallai and Havel-Hakimi algorithms. Acta Univ. Sapientiae, Inform. 3, 2 (2011) 230-268. ⇒ 256, 259, 260, 262, 275 Search in Google Scholar

[49] A. Iványi, S. Pirzada. Comparison based ranking, in: ed. A. Iványi, Algorithms of Informatics, Vol. 3, mondAt, Vác, 2013, 1209-1258. ⇒260Search in Google Scholar

[50] A. E. Kézdy, J. Lehel, Degree sequences of graphs with prescribed clique size. In: Y. Alavi et. al. (eds.) Combinatorics, Graph Theory, and Algorithms, vol. 2., Michigan, New Issues Press, Kalamazoo, 1999, 535-544. ⇒260Search in Google Scholar

[51] D. J. Kleitman, D. L. Wang, Algorithm for constructing graphs and digraphs with given valences and factors, Discrete Math., 6 (1973) 79-88. ⇒254, 257, 25810.1016/0012-365X(73)90037-XSearch in Google Scholar

[52] D. Kratsch, R. M. McConnell, K. Mehlhorn, J. P. Spinrad, Certifying algorithms for recognizing interval graphs and permutation graphs, SIAM J. Comput., 36, (2) (2006) 326-353. ⇒26610.1137/S0097539703437855Search in Google Scholar

[53] D. Kratsch, J. Lehel, H. Müller, Toughness, hamiltonicity and split graphs, Discrete Math., 150 (1996) 231-245. ⇒26610.1016/0012-365X(95)00190-8Search in Google Scholar

[54] M. D. Lamar, Split digraphs, Discrete Math., 312, (7) (2012) 1314-1325. ⇒26610.1016/j.disc.2011.12.023Search in Google Scholar

[55] V. B. Le, H. N. de Ridder, Probe split graphs, Discrete Math. Theor. Comput. Sci., 9(1), (2007) 207-238. ⇒25510.46298/dmtcs.401Search in Google Scholar

[56] J. S. Li, Z. X. Song, An extremal problem on the potentially pk-graphic sequence, Discrete Math., 212 (2000) 223-231. ⇒264Search in Google Scholar

[57] J. S. Li, Z. X. Song, R. Luo, The Erdős-Jacobson-Lehel conjecture on potentially pk-graphic sequences is true, Sci. China Ser. A, 41 (1998) 510-520. ⇒264Search in Google Scholar

[58] F. Maffray, M. Preissmann, Linear recognition of pseudo-split graphs, Discrete Appl. Math. 52 (1994) 307-312. ⇒263, 27910.1016/0166-218X(94)00022-0Search in Google Scholar

[59] R. M. McConnell, K. Mehlhorn, S. Näher, P. Schweitzer, Certifying algorithms, Computer Science Review, 5, (2) (2011) 119-161. ⇒260Search in Google Scholar

[60] C. McCreesh, Multi-threaded maximum clique, level 4 Project, School of Computing Science, of Glasgow University, 2013, 38 pages. ⇒264Search in Google Scholar

[61] F. R. McMorris, C. Wang, P. Zhang, On probe interval graphs, Discrete Appl. Math., 88(1-3), (1998) 315-324. ⇒255Search in Google Scholar

[62] S. D. Nikolopoulos, Constant-time parallel recognition of split graphs, Inf. Proc. Letters, 54, (1) (1995) 1-8. ⇒265Search in Google Scholar

[63] P. M. Pardalos, J. Rappe, M. G. S. Resende, An exact parallel algorithm for the maximum clique problem, High Performance Algorithms and Software in Nonlinear Optimization, Applied Optimization, 24 (1998) 279-300. ⇒264Search in Google Scholar

[64] P. M. Pardalos, J. Xue, The maximum clique problem, J. Global Opt. (1994) 301-328. ⇒264Search in Google Scholar

[65] J. Peemüller, necessary conditions for hamiltonian split graphs, Discrete Math., 54 (1985) 45-57. ⇒265, 266Search in Google Scholar

[66] S. Pirzada, An Introduction to Graph Theory, Universities Press, Orient Blackswan, India, 2012. ⇒253Search in Google Scholar

[67] S. Pirzada, B. A. Chat, Potentially graphic sequences of split graphs, Kragujevac J. Math., 38, (1) (2014) 73-81. ⇒255, 256, 262, 263Search in Google Scholar

[68] A. R. Rao, The clique number of a graph with given degree sequence, in: A. R. Rao (Ed.) Proc. Symp. on Graph Theory, MacMillan and Co. Limited, India, ISI Lecture Notes Series, 4 (1979) 251-267. ⇒260 Search in Google Scholar

[69] A. R. Rao, A survey of the theory of potentially P-graphic and forcibly P-graphic degree sequences, Comb. Graph Theory, Proc. Symp. (Calcutta 1980), Lect. Notes Math. 885 (1981) 417-440. ⇒26010.1007/BFb0092288Search in Google Scholar

[70] A. R. Rao, An Erdős-Gallai type result on the clique number of a realization of a degree sequence (unpublished). ⇒260Search in Google Scholar

[71] G. F. Royle, Counting set covers and split graphs, J. Integer Sequences, 3 (2000), Article 00.2.6, 5 pages. ⇒264Search in Google Scholar

[72] M. C. Schmidt, N. F. Samatova, K. Thomas, B.-H. Park, A scalable, parallel algorithm for maximal clique enumeration, J. Parallel Dist. Comp., 69, (4) (2009) 417-428. ⇒264Search in Google Scholar

[73] P. S. Segundo, D. Rodríguez-Losada, A. Jim´enez, An exact bit-parallel algorithm for the maximum clique problem, Computers & Operations Res., 38, (2) (2011) 571-581. ⇒264Search in Google Scholar

[74] N. J. A. Sloane, The number of degree-vectors for simple graphs. In (ed. N. J. A. Sloane): The On-Line Encyclopedia of the Integer Sequences. 2014, http://oeis.org/A004251 . ⇒260Search in Google Scholar

[75] S. Szabó, Parallel algorithms for finding cliques in a graph, J. Physics: Conf. Series, 268, (1) (2011) 012030. ⇒264Search in Google Scholar

[76] E. Tomita, A. Tanaka, H. Takahashi, The worst-case time complexity for generating all maximal cliques and computational experiments, Theoretical Computer Science, 363, (1) (2006) 28-42. ⇒264Search in Google Scholar

[77] A. Tripathi, H. Tyagi, A simple criterion on degree sequences of graphs. Discrete Appl. Math., 156, 18 (2008) 3513-3517. ⇒258Search in Google Scholar

[78] A. Tripathi, S. Venugopalan, D. B. West, A short constructive proof of the Erdős-Gallai characterization of graphic lists, Discrete Math., 310, (4) (2010) 843-844. ⇒258Search in Google Scholar

[79] R. I. Tyshkevich, The canonical decomposition of a graph, Doklady Akademii Nauk SSSR (in Russian), 24 (1980) 677-679. ⇒263Search in Google Scholar

[80] R. I. Tyshkevich, A. A. Chernyak, Yet another method of enumerating unmarked combinatorial objects, Mathematical Notes, 48, (6) (1990) 1239-1245 and (in Russian) Mat. Zametki, 48, (6) (1990) 98-105. ⇒264Search in Google Scholar

[81] R. I. Tyshkevich, O. I. Melnikow, V. M. Kotov, On graphs and degree sequences: the canonical decomposition (in Russian), Kibernetica, 6 (1981) 5-8. ⇒263Search in Google Scholar

[82] Wikipedia, Split graph. http://en.wikipedia.org/wiki/Splitgraph, 2014. ⇒256, 263Search in Google Scholar

[83] G. J. Woeginger, The taughness of split graphs, Discrete Math., 190 (1998) 195-197. ⇒266Search in Google Scholar

[84] J.-H. Yin, Conditions for r-graphic sequences to be potentially K(r) m+1-graphic, Discrete Math., 309 (2009) 6271-6276. ⇒261Search in Google Scholar

[85] J.-H. Yin, A generalization of a conjecture due to Erdős, Jacobson and Lehel, Discrete Math., 309 (2009) 2579-2583. ⇒261, 264Search in Google Scholar

[86] J.-H. Yin, A Rao-type characterization for a sequence to have a realization containing a split graph, Discrete Math., 311 (2011) 2485-2489. ⇒255, 256 Search in Google Scholar

[87] J.-H. Yin, A Havel-Hakimi type procedure and a sufficient condition for a sequence to be potentially Sr,s-graphic, Czechoslovak Math. J., 62, (3) (2012) 863-867. ⇒255, 256, 262, 279Search in Google Scholar

[88] J.-H. Yin, An extension of A. R. Rao’s characterization of potentially Km+1- graphic sequences, Discrete Appl. Math., 161, (7-8) (2013) 1118-1127. ⇒256, 262Search in Google Scholar

[89] J.-H. Yin, A Rao-type characterization for a sequence to have a realization containing an arbitrary subgraph H, Acta Math. Sin., 30, (3) (2014) 389-394. ⇒ 262Search in Google Scholar

[90] J.-H. Yin, Y.-S. Li, Two sufficient conditions for a graphic sequence to have a realization with prescribed clique size, Discrete Math., 209 (2005) 218-227. ⇒ 264Search in Google Scholar

[91] B. Zavalnij, Three versions of clique search parallelization, J. Comp. Sci. Inf. Technology, 2(2), (2014) 9-20. ⇒264 Search in Google Scholar