On vertex independence number of uniform hypergraphs

[1] V. Abraham, Independence in hypergraphs. J. Indian Math. Soc. (N.S.), 78, 1-4 (2011) 1-7. ⇒141Search in Google Scholar

[2] B. D. Acharya, Interrelations among the notions of independence, domination and full sets in a hypergraph, Nat. Acad. Sci. Lett. 13, 11 (1990) 421-422. ⇒ 142Search in Google Scholar

[3] G. Agnarsson, A. Egilsson, M. M. Halldórson, Vertex coloring acyclic digraphs and their corresponding hypergraphs, Discrete Appl. Math. 156, 10 (2008) 1918-1928. ⇒142Search in Google Scholar

[4] G. Agnarsson, M. M. Halldórson, E. Losievskaja, SDP-based algorithms for maximum independent set problems on hypergraphs, in: Automata, Languages and Programming. Part I, Lecture Notes in Comput. Sci. 5555, Springer, Berlin, 2009, 12-23. ⇒133, 138, 14110.1007/978-3-642-02927-1_3Search in Google Scholar

[5] G. Agnarsson, M. M. Halldórson, E. Losievskaja, SDP-based algorithms for maximum independent set problems on hypergraphs, Theoret. Comp. Sci. 470 (2013) 1-9. ⇒133, 138, 14110.1016/j.tcs.2012.11.025Search in Google Scholar

[6] M. Ajtai, P. Erdős, J. Komlós and E. Szemerédi, On Turán theorem for sparse graphs, Combinatorica 1, 3 (1981) 313-317. ⇒13410.1007/BF02579451Search in Google Scholar

[7] M. Ajtai, P. Erdős, J. Komlós, E. Szemerédi, A dense infinite Sidon sequence, European J. Combin. 2, 1 (1981) 1-11. ⇒13410.1016/S0195-6698(81)80014-5Search in Google Scholar

[8] M. Ajtai, J. Komlós and E. Szemerédi, A note on Ramsey numbers, J. Combin. Theory Ser. A 29 (1980) 354-360. ⇒13410.1016/0097-3165(80)90030-8Search in Google Scholar

[9] A. Alon, A fast and simple randomized parallel algorithm for the maximal independent set problem, J. Algorithms 7, 4 (1986) 567-583. ⇒133, 13810.1016/0196-6774(86)90019-2Search in Google Scholar

[10] N. Alon, P. Frankl, H. Huang, V. Rödl, A. Ruciński, Large matchings in uniform hypergraphs and the conjectures of Erdős and Samuels, J. Combin. Theory Ser. A 119, 6 (2012) 1200-1215. ⇒133, 138, 14210.1016/j.jcta.2012.02.004Search in Google Scholar

[11] N. Alon, J. H. Spencer, The Probabilistic Method, Wiley-Interscience, New York, 1992. ⇒134Search in Google Scholar

[12] A. Alon, A. Uri, Y. Azar, Independent sets in hypergraphs with applications to routing via fixed paths. In: Randomization, approximation, and combinatorial optimization (Berkeley, CA, 1999), Lecture Notes in Comput. Sci. 1671, Springer, Berlin, 1999, 16-27. ⇒14110.1007/978-3-540-48413-4_3Search in Google Scholar

[13] N. Alon, R. Yuster, On a hypergraph matching problem, Graphs Comb. 21 (2005) 377-384. ⇒14210.1007/s00373-005-0628-xSearch in Google Scholar

[14] E. Angel, R. Campigotto, C. Laforest, A new lower bound on the independence number of graphs, Discrete Appl. 161, 6 (2013) 847-852. ⇒13410.1016/j.dam.2012.10.001Search in Google Scholar

[15] G. Ausiello, A. D’Atri, D. Sacc`a, Minimal representation of directed hypergraphs, SIAM J. Comput. 15 (1986) 418-431. ⇒13910.1137/0215029Search in Google Scholar

[16] J. Bailey, T. Manoukian, K. Ramamohanaro, A fast algorithm for computing hypergraph transversals and its application in mining emerging patterns, in: Proc. of the Third IEEE Int.l Conf. on Data Mining (ICDM03), 2003, 485-488. ⇒142Search in Google Scholar

[17] J. Balogh, J. Butterfield, P. Hu, J. Lenz, D. Mubayi, On the chromatic thresholds of hypergraphs arXiv:1103.1416, 2013, 37 pages. ⇒142Search in Google Scholar

[18] J. Balogh, R. Morris, W. Samotij, Independent sets in hypergraphs, arXiv:1204.6530, 2013, 42 pages. ⇒136Search in Google Scholar

[19] Zs. Baranyai, On the factorization of the complete uniform hypergraph, in: A. Hajnal, R. Rado, V. T. Sós (Eds.), Infinite and Finite Sets, Proc. Coll. Keszthely, 1973, North-Holland, Amsterdam, Netherlands, 1975, pp. 91-108. ⇒142Search in Google Scholar

[20] S. Behrens, C. Erbes, M. Ferrara, S. G. Hartke, B. Reiniger, H. Spinoza, C. Tomlinson, New results on degree sequences of uniform hypergraphs. Electron. J. Combin. 20, 4 (2013) #P14, 18 pages. ⇒139Search in Google Scholar

[21] M. Behrisch, A. Coja-Oghlan, M. Kang, The asymptotic number of connected d-uniform hypergraphs, Combin. Probab. Comput. 23, 3 (2014) 367-385. ⇒13910.1017/S0963548314000029Search in Google Scholar

[22] C. Berge, The Theory of Graphs and its Applications, Wiley, London, 1964. ⇒ 137Search in Google Scholar

[23] E. Berger, R. Ziv, A note on the edge cover number and independence number in hypergraphs, Discrete Math. 308, 12 (2008) 2649-2654. ⇒14110.1016/j.disc.2007.05.006Search in Google Scholar

[24] C. Bertram-Kretzberg, H. Lefmann, The algorithmic aspects of uncrowded hypergraphs. SIAM J. Comput. 29, 1 (1999) 201-230. ⇒14210.1137/S0097539797323716Search in Google Scholar

[25] T. Biedl, E. D. Demaine, C. A. Duncan, R. Fleischer, S. G. Kobourov, Tight bounds on maximal and maximum matchings, Discrete Math. 285 (2004) 7-15. ⇒14110.1016/j.disc.2004.05.003Search in Google Scholar

[26] V. Blinovsky, Fractional matching in hypergraphs, arXiv:1311.2671, 2013, 6 pages. ⇒141Search in Google Scholar

[27] B. Bollobás, D. E. Daykin, P. Erdős, Sets of independent edges of a hypergraph, Quart. J. Math. Oxford Ser. (2) 27, 1 (1976), 25-32. ⇒14110.1093/qmath/27.1.25Search in Google Scholar

[28] A. Bonato, J. I. Brown, D. Mitsche, P. Pralat, Independence densities of hypergraphs, arXiv:1308.2837, 2013, 16 pages. ⇒141Search in Google Scholar

[29] A. Bonato, J. I. Brown, D. Mitsche, P. Pralat, Independence densities of hypergraphs, Europ. J. Combin. 40 (2014) 124-136. ⇒14110.1016/j.ejc.2014.03.001Search in Google Scholar

[30] R. Boppana, M. M. Halldórson, Approximating maximum independent set by excluding subsets, BIT, 32 (1992) 160-196. ⇒133, 138Search in Google Scholar

[31] M. Bordewich, M. Dyer, M. Karpiński, Path coupling using stopping times and counting independent sets and colorings in hypergraphs Random Structures Alg. 32, 3 (2008) 375-399. ⇒14110.1002/rsa.20204Search in Google Scholar

[32] E. Boros, K. Elbassioni, V. Gurvich, L. Khachiyan,Generating maximal independent sets for hypergraphs with bounded edge-intersections. In: LATIN 2004: Theoretical informatics, Lecture Notes in Comput. Sci. 2976, Springer, Berlin, 2004, 488-498. ⇒14110.1007/978-3-540-24698-5_52Search in Google Scholar

[33] E. Boros, V. Gurvich, K. Elbassioni, L. Khachiyan, An efficient incremental algorithm for generating all maximal independent sets in hypergraphs of bounded dimension. Parallel Process. Lett. 10, 4 (2000) 253-266. ⇒14110.1142/S0129626400000251Search in Google Scholar

[34] M. Borowiecki, D. Michalak, The independence graphs of hypergraphs and middle graphs, Discuss. Math. 7 (1985) 31-37. ⇒141Search in Google Scholar

[35] Cs. Bujtás, Zs. Tuza, Uniform mixed hypergraphs: The possible numbers of colors, Graphs Combin., 24 (2008) 1-12. ⇒14210.1007/s00373-007-0765-5Search in Google Scholar

[36] Y. Caro, New results on the independence number, Technical Report, 1979, Tel- Aviv University. ⇒134Search in Google Scholar

[37] Y. Caro, A. Hansberg, New approach to the k-independence number of a graph. Electron. J. Combin. 20, 1 (2013) #P33, 17 pages. ⇒13510.37236/2646Search in Google Scholar

[38] Y. Caro, Zs. Tuza, Improved lower bounds on k-independence, J. Graph Theory 15 (1991) 99-107. ⇒13510.1002/jgt.3190150110Search in Google Scholar

[39] R. D. Carr, G. Lancia, S. Istrail, C. Genomics, Branch-and-Cut algorithms for independent set problems: Integrality gap and an application to protein structure alignment. SAND Report SAND2000-2171, Sandia National Laboratories, 2000. ⇒14210.2172/764804Search in Google Scholar

[40] G. Chartrand, S. Schuster, On the independence number of complementary graphs, Trans. New York Acad. Sci., Series II 36, 3 (1974) 247-251. ⇒13910.1111/j.2164-0947.1974.tb01571.xSearch in Google Scholar

[41] M. Chellali, O. Favaron, A. Hansberg, L. Volkmann, k-domination and kindependence in graphs: a survey, Graphs Combin. 28, 1 (2012) 1-55. ⇒135, 13710.1007/s00373-011-1040-3Search in Google Scholar

[42] M. Chellali, N. J. Rad, On k-independence critical graphs. Australas. J. Combin. 53 (2012) 289-298. ⇒135Search in Google Scholar

[43] E. J. Cockayne, S. T. Hedetniemi, R. Laskar, Gallai theorems for graphs, hypergraphs and set systems, Discrete Math. 72 (1988) 35-47. ⇒14210.1016/S0167-5060(08)70769-6Search in Google Scholar

[44] B. Csaba, T. A. Pick, A Shokoufandeh, A note on the Caro-Tuza bound on the independence number of uniform hypergraphs, Australas. J. Combin. 52 (2012) 235-242. ⇒135Search in Google Scholar

[45] J. Cutler, A. J. Radcliffe, Hypergraph independent sets, Combin. Probab. Comput. 22, 1 (2013) 9-20. ⇒14110.1017/S0963548312000454Search in Google Scholar

[46] B. C. Dean, S. M. Hedetniemi, S. T. Hedetniemii, J. Lewis, A. McRae, Matchability and k-maximal matchings. Discrete Math. 159, 1 (2011) 15-22. ⇒14110.1016/j.dam.2010.09.006Search in Google Scholar

[47] A. Dudek, A. Frieze, A. Ruciński, M. ˇSileikis, Approximate counting of regular hypergraphs, Inf. Processing Letters, 113, 1921 (2013) 785-788. ⇒139, 14110.1016/j.ipl.2013.07.018Search in Google Scholar

[48] K. Dutta, D. Mubayi, C. R. Subramanian, New lower bounds for the independence number of sparse graphs and hypergraphs. SIAM J. Discrete Math. 26, 3 (2012) 1134-1147. ⇒13810.1137/110839023Search in Google Scholar

[49] J. Edmonds, Paths, trees, and flowers, Canadian J. Math. 17 (1965) 449-467. ⇒133, 138, 14110.4153/CJM-1965-045-4Search in Google Scholar

[50] J. Edmonds, Maximal matching and a polyhedron with 0, 1-vertices, J. Research Nat. Bureau Standards B-69 (1965) 125-130. ⇒133, 138, 14110.6028/jres.069B.013Search in Google Scholar

[51] A. Eustis, Hypergraph Independence Numbers, PhD Thesis. University of California, San Diego. 2013. 123 pages. ⇒138Search in Google Scholar

[52] A. Eustis, J. Verstra¨ete, On the independence number of Steiner systems, Combinatorics, Prob. Comp. 22, 2 (2013) 241-252. ⇒13810.1017/S0963548312000557Search in Google Scholar

[53] S. Fajtlowicz, Independence, clique size and maximum degree, Combinatorica 4 (1984), 35-38. ⇒13610.1007/BF02579154Search in Google Scholar

[54] O. Favoron, A. Hansberg, L. Volkmann, On k-domination and minimum degree in graphs, J. Graph Theory 57, 1 (2008) 33-40. ⇒135, 13710.1002/jgt.20279Search in Google Scholar

[55] A. Frank, T. Király, Z. Király, On the orientation of graphs and hypergraphs, Discrete Appl. Math 131, 2 (2003) 385-400. ⇒140, 14210.1016/S0166-218X(02)00462-6Search in Google Scholar

[56] P. Frankl, Improved bounds for Erdős matching conjecture, J. Combin. Theory Ser. A 120, 5 (2013) 1068-1072. ⇒14110.1016/j.jcta.2013.01.008Search in Google Scholar

[57] P. Frankl, T. Luczak, K.Mieczkowska, On matchings in hypergraphs. Electron. J. Combin. 19, 2 (2012), #P42, 5 pages. ⇒14110.37236/2176Search in Google Scholar

[58] P. Frankl, V. Rödl, Some Ramsey-Turn type results for hypergraphs. Combinatorica 8, 4 (1988) 323-332. ⇒14210.1007/BF02189089Search in Google Scholar

[59] P. Frankl, V. Rödl, The uniformity lemma for hypergraphs, Graphs Combin. 8 (1992) 309-312. ⇒14210.1007/BF02351586Search in Google Scholar

[60] M. Frieze, On the independence number of random graphs, Discrete Math. 81, 2 (1990) 171-175. ⇒13610.1016/0012-365X(90)90149-CSearch in Google Scholar

[61] Z. FÜredi, Matchings and covers in hypergraphs, Graphs Combin. 4 (1988) 115-206. ⇒14110.1007/BF01864160Search in Google Scholar

[62] Z. Füredi, The number of maximal independent sets in connected graphs, J. Graph Theory, 11, 4 (1995) 463-470. ⇒13710.1002/jgt.3190110403Search in Google Scholar

[63] Z. FÜredi, Linear trees in uniform hypergraphs, Europ. J. Combin. 35 (2014) 264-272. ⇒14210.1016/j.ejc.2013.06.022Search in Google Scholar

[64] Z. Füredi, M. Ruszinkó, Uniform hypergraphs containing no grids, Adv. Math. 240 (2013) 302-324. ⇒14210.1016/j.aim.2013.03.009Search in Google Scholar

[65] H. M. Gabow, An efficient implementation of Edmonds’ algorithm for maximum matching on graphs, J. ACM 23, 2 (1976) 221-234. ⇒14110.1145/321941.321942Search in Google Scholar

[66] H. M. Gabow, Data structures for weighted matchings and nearest nearest common ancestors with linking, in: Proc. 1st Annual ACM-SIAM Symp. Discrete Algorithms 1990, 434-443. ⇒141Search in Google Scholar

[67] T. Gallai, Über extreme Punkt- und Kantenmengen, Ann. Univ. Sci. Budapest. de Rolando Eötvös Nominatae, Sect. Math. 2 (1959) 133-138. ⇒139Search in Google Scholar

[68] G. Gallo, G. Longo, S. Nguyen, S. Pallottino, Directed hypergraphs and applications, Discrete Appl. Math 42, 2-3 (1993) 177-201. ⇒140, 14210.1016/0166-218X(93)90045-PSearch in Google Scholar

[69] S.. Gaspers, D. Kratsch, M. Liedloff, Independent sets and bicliques in graphs, in: H. Broersma, T. Erlebach, T. Friedetzky, D. Paulusma (eds.) Graph-Theoretic Concepts in Computer Science (Int. Workshop WG2008, Durham, UK, June 30, 2008-July 2, 2008), Lecture Notes in Comput. Sci. 5344, Springer, 2008, 171-182. ⇒13610.1007/978-3-540-92248-3_16Search in Google Scholar

[70] C. Greenhill, The complexity of counting colourings and independent sets in sparse graphs and hypergraphs. Comput. Complexity 9, 1 (2000) 52-72. ⇒14110.1007/PL00001601Search in Google Scholar

[71] C. Greenhill, A. Rucinski, N. C. Wormald, Random hypergraph processes with degree restrictions, Graphs Combin. 20 (2004) 319-332. ⇒14110.1007/s00373-004-0571-2Search in Google Scholar

[72] J. Griggs, Lower bounds on the independence number in terms of the degrees, J. Comb. Theory, Ser. B 34 (1983) 22-39. ⇒134, 14510.1016/0095-8956(83)90003-5Search in Google Scholar

[73] J. L. Gross, J. Yellen, P. Zhang, Handbook of Graph Theory, CRC Press, Boca Raton, FL, 2014. ⇒133, 13810.1201/b16132Search in Google Scholar

[74] D. Gunopolus, R. Khardon, H. Mannila, H. Toivonen, Data mining, hypergraph traversals, and machine learning. Proc. PODS’97, 1997, pp. 209-2016. ⇒14210.1145/263661.263684Search in Google Scholar

[75] M. M. Halldórson, Approximations of weighted independent set and hereditary subset problems, J. Graph Algorithms Appl. 4, 1 (2000) 1-16. ⇒13610.7155/jgaa.00020Search in Google Scholar

[76] M. M. Halldórson, E. Losievskaja, Independent sets in bounded-degree hypergraphs, Discrete Appl. Math 157, 8 (2009) 1773-1786. ⇒14110.1016/j.dam.2008.11.013Search in Google Scholar

[77] J. Han, Near perfect matchings in k-uniform hypergraphs, arXiv:1404.1136, 2014, 7 pages. ⇒141Search in Google Scholar

[78] H. Hàn, Y. Person, M. Schaht, On perfect matchings in uniform hypergraphs with large minimum vertex degree, SIAM J. Discrete Math. 23, 2 (2009) 732-748. ⇒141, 14210.1137/080729657Search in Google Scholar

[79] A. Hansberg, R. Pepper, On k-domination and j-independence in graphs. Discrete Appl. Math 161, 10-11 (2013) 1472-1480. ⇒135, 136, 13710.1016/j.dam.2013.02.008Search in Google Scholar

[80] J. Harant, A lower bound on independence number of a graph, Discrete Math. 188, 13 (1998) 239243. ⇒13410.1016/S0012-365X(98)00048-XSearch in Google Scholar

[81] J. Harant, A lower bound on independence in terms of degrees, Discrete Appl. Mathematics 159, 10 (2011) 966-970. ⇒134, 13510.1016/j.dam.2011.03.003Search in Google Scholar

[82] J. Harant, A. Pruchnewski, M. Voigt, On dominating sets and independent sets of graphs, Combinatorics, Prob. Comp. 8, 6 (1999) 547-553. ⇒13710.1017/S0963548399004034Search in Google Scholar

[83] J. Harant, D. Rautenbach, Independence in connected graphs. Discrete Appl. Math 159, 1 (2011) 79-86. ⇒13510.1016/j.dam.2010.08.029Search in Google Scholar

[84] J. Harant, I. Schiermeyer, On the independence number of a graph in terms of order and size, Discrete Math., 232, 1-3 (2001) 131-138. ⇒13510.1016/S0012-365X(00)00298-3Search in Google Scholar

[85] J. Harant, I. Schiermeyer, A lower bound on the independence number of a graph in terms of degrees. Discuss. Math. Graph Theory 26, 3 (2006), 431-437. ⇒13510.7151/dmgt.1335Search in Google Scholar

[86] M. A. Henning, C. Löwenstein, D. Rautenbach, Independent sets and matchings in subcubic graphs. Discrete Math., 312, 11 (2012) 1900-1910. ⇒14110.1016/j.disc.2012.03.002Search in Google Scholar

[87] M. A. Henning, C. Löwenstein, J. Southey, A. Yeo. A new lower bound on the independence number of a graph and applications, Electron. J. Comb. 21, 1 (2014) #P1.38. ⇒13610.37236/3601Search in Google Scholar

[88] M. A. Henning, A. Yeo, Tight lower bounds on the size of a maximum matching in a regular graph. Graphs Combin. 3, 6 (2007) 647-657. ⇒14110.1007/s00373-007-0757-5Search in Google Scholar

[89] M. A. Henning, A. Yeo, Lower bounds on the size of maximum independent sets and matchings in hypergraphs of rank three. J. Graph Theory, 72, 1-2 (2013) 220-245. ⇒135, 141, 14210.1002/jgt.21640Search in Google Scholar

[90] T. Hofmeister, H. Lefmann, Approximating maximum independent sets in uniform hypergraphs. In: Mathematical Foundations of Computer Science, 1998, Brno, Lecture Notes in Comput. Sci. 1450, Springer, Berlin, 1998, 562-570. ⇒ 14110.1007/BFb0055806Search in Google Scholar

[91] J. E. Hopcroft, R. M. Karp, An n5/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput., 2 (1973) 225-231. ⇒14110.1137/0202019Search in Google Scholar

[92] H. Huang, P.-S. Loh, B. Sudakov, The size of a hypergraph and its matching number, Combin. Probab. Comput. 21, 3 (2012) 442-450. ⇒141, 14210.1017/S096354831100068XSearch in Google Scholar

[93] D. S. Johnson, M. Yannakakis, On generating all maximal independent sets, Inf. Processing Letters 27, 3 (1988) 119-123. ⇒133, 138, 141, 14210.1016/0020-0190(88)90065-8Search in Google Scholar

[94] T. Johnston, L. Lu, Turn problems on non-uniform hypergraphs, arXiv:1301.1870, 2013. ⇒14210.37236/3901Search in Google Scholar

[95] T. Johnston, L. Lu, Strong jumps and Lagrangians of non-uniform hypergraphs, arXiv:1403.1220, 2014. ⇒14210.37236/3901Search in Google Scholar

[96] B. K. Jose, Zs. Tuza, Hypergraph domination and strong independence. Appl. Anal. Discrete Math. 3, 2 (2009) 347-358. ⇒14210.2298/AADM0902347JSearch in Google Scholar

[97] E. Jucovič, F. Olejník, On chromatic and achromatic numbers of uniform hypergraphs, Časopis Pĕstováni Matematiky, 99 (1974) 123-130. ⇒139, 14210.21136/CPM.1974.117834Search in Google Scholar

[98] A. Kako, T. Ono, T. Hirata, M. M. Halldórson, Approximation algorithms for the weighted independent set problem in sparse graphs, Discrete Appl. Math 157, 4 (2009) 617-626. ⇒13610.1016/j.dam.2008.08.027Search in Google Scholar

[99] M. Karonski, T. Luczak, The number of connected sparsely edged uniform hypergraphs, Discrete Math. 171, 1-3 (1997) 153-167. ⇒14210.1016/S0012-365X(96)00076-3Search in Google Scholar

[100] R.M. Karp, U.V. Vazirani, V.V. Vazirani, An optimal online algorithm for optimal bipartite matching, in: Proceedings of the Twenty-second Annual ACM Symposium on Theory of Computing (STOC ’90), ACM, New York, NY, 1990, 352-358. ⇒14110.1145/100216.100262Search in Google Scholar

[101] R. M. Karp, A. Widgerson, A fast parallel algorithm for the maximal independent set problem, J. ACM 32, 4 (1985) 762-773. ⇒133, 13810.1145/4221.4226Search in Google Scholar

[102] G. O. H. Katona, Continuous versions of some extremal hypergraph problems, in: Combinatorics (Keszthely, Hungary, 1976), Coll. Math. Soc. J. Bolyai 18 (Math. Soc. J. Bolyai, Budapest, 1978), 653-678. ⇒142Search in Google Scholar

[103] G. O. H. Katona, Continuous versions of some extremal hypergraph problems II, Acta Math. Acad. Sci. Hungar. 35 (1980) 67-77. ⇒14210.1007/BF01896826Search in Google Scholar

[104] P. Keevash, F. Knox, R. Mycroft, Polynomial-time perfect matchings in dense hypergraphs, arXiv:1307.2608, 2013. 62 pages. ⇒14110.1145/2488608.2488647Search in Google Scholar

[105] P. Keevash, R. Mycroft, A geometric theory for hypergraph matching, arXiv:1108.1757, 2013, 101 pages. ⇒14110.1007/978-88-7642-475-5_23Search in Google Scholar

[106] P. Keevash, B. Sudakov, On a hypergraph Turán problem of Frankl, Combinatorica 25, 6 (2005) 673-706. ⇒14210.1007/s00493-005-0042-2Search in Google Scholar

[107] P. Kelsen, On the parallel complexity of computing a maximal independent set in a hypergraph. In: Proc. Twenty-fourth Annual ACM Symp. Theory Comp. (STOC’92), ACM New York, NY, 1992, 339-350. ⇒138, 14210.1145/129712.129745Search in Google Scholar

[108] L. Khachiyan, E. Boros, V. Gurvich, K. Elbassioni, Computing many maximal independent sets for hypergraphs in parallel, Parallel Process. Lett. 17, 2 (2007) 141-152. ⇒14110.1142/S0129626407002934Search in Google Scholar

[109] I. Khan, Perfect matchings in 3-uniform hypergraphs with large vertex degree. SIAM J. Discrete Math. 27, 2 (2013) 1021-1039. ⇒14110.1137/10080796XSearch in Google Scholar

[110] M. A. Khan, S. , K. K. Kayibi, Scores, inequalities and regular hypertournaments, Math. Inequal. Appl. 15, 2 (2012), 343-351. ⇒13910.7153/mia-15-28Search in Google Scholar

[111] Y. Kohayakawa, V. Rödl, J. Skokan, Hypergraphs, quasi-randomness, and conditions for regularity, J. Combin. Theory Ser. A 97, 2 (2002) 307-352. ⇒14210.1006/jcta.2001.3217Search in Google Scholar

[112] V. Kolmogorov, V. Blossom, A new implementation of a minimum cost perfect matching algorithm, Math. Programming Pomp. 1 (2009) 43-67. ⇒14110.1007/s12532-009-0002-8Search in Google Scholar

[113] D. Kőnig, Graphs and matrices (Hungarian), Matematikai és Fizikai Lapok 38 (1931) 116-119. ⇒141Search in Google Scholar

[114] A. Kostochka, D. Mubayi, J. Verstra¨ete, On independent sets in hypergraphs, Random Structures Algorithms 44, 2 (2014) 224-239. ⇒14210.1002/rsa.20453Search in Google Scholar

[115] M. Krivelevich, Approximate set covering in uniform hypergraphs, J. Algorithms 25, 1 (1997) 118-143. ⇒14210.1006/jagm.1997.0872Search in Google Scholar

[116] M. Krivelevich, R. Nathaniel, B. Sudakov, Approximating coloring and maximum independent sets in 3-uniform hypergraphs, J. Algorithms 41, 1 (2001) 99-113. ⇒14210.1006/jagm.2001.1173Search in Google Scholar

[117] D. KÜhn, D. Loose, Hamilton cycles in 3-uniform hypergraphs of high minimum degree, J. Comb. Theory, Ser. B 96, 6 (2006) 767-821. ⇒14210.1016/j.jctb.2006.02.004Search in Google Scholar

[118] D. KÜhn, D. Osthus, A. Treglown, Matchings in 3-uniform hypergraphs, J. Combinatorial Theory Series B 103 (2013) 291-305. ⇒14110.1016/j.jctb.2012.11.005Search in Google Scholar

[119] D. KÜhn, D. Osthus, T. Townsend, Fractional and integer matchings in uniform hypergraphs, Europ. J. Combin. 38 (2014) 83-96. ⇒14110.1016/j.ejc.2013.11.006Search in Google Scholar

[120] R. Laskar, B. Auerbach, On complementary graphs with no isolated vertices, Discrete Math. 24, 2 (1978) 113-118. ⇒14010.1016/0012-365X(78)90189-9Search in Google Scholar

[121] E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, Generating all maximal independent sets: NP-hardness and polynomial-time algorithms, SIAM J. Comput. 9, 3 (1980), 558-565. ⇒133, 13810.1137/0209042Search in Google Scholar

[122] V. V. Lepin, An algorithm for finding the independence number of a recursively generated hypergraph (Russian), Dokl. Nats. Akad. Nauk Belarusi 49, 2 (2005), 22-25, 125. ⇒141Search in Google Scholar

[123] Y. Li, C. Rousseau, On book-complete graph Ramsey numbers, J. Comb. Theory, Ser. B 68, 1 (1996) 36-44. ⇒14210.1006/jctb.1996.0055Search in Google Scholar

[124] Y. Li, C. Rousseau, W. Zang, Asymptotic upper bound for Ramsey functions, Graphs Combin., 17 (2001) 123-128. ⇒14210.1007/s003730170060Search in Google Scholar

[125] Y. Li, W. Zang, Differential methods for finding independent sets in hypergraphs, SIAM J. Discrete Math. 20 (2006) 96-104. ⇒141, 14210.1137/S0895480104442571Search in Google Scholar

[126] E. Losievskaja, Approximation Algorithms for Independent Set Problems on Hypergraphs, PhD Dissertation, School of Computer Science Reykjavik University, Reykyavik, 2009, XV + 80 pages. ⇒133, 138, 141Search in Google Scholar

[127] L. Lovász, M. D. Plummer, Matching Theory, North Holland, Amsterdam, 1986. ⇒141Search in Google Scholar

[128] M. Luby, A simple parallel algorithm for the maximal independent set problem, SIAM J. Comput. 15, 1 (1976) 1036-1053. ⇒133, 13810.1137/0215074Search in Google Scholar

[129] T. Luczak, E. Szymańska, A parallel randomized algorithm for finding a maximal independent set in a linear hypergraph, J. Algorithms 25, 2 (1997) 311-320. ⇒14210.1006/jagm.1997.0884Search in Google Scholar

[130] D. Maier, Minimum covers in the relational data base model, J. Assoc. Comp. Mach. 27 (1980) 664-674. ⇒14210.1145/322217.322223Search in Google Scholar

[131] K. Markström, A. Ruciński, Perfect matchings (and Hamilton cycles) in hypergraphs with large degrees, Europ. J. Combin. 32, 5 (2011) 677-687. ⇒14110.1016/j.ejc.2011.02.001Search in Google Scholar

[132] S. Micali, V.V. Vazirani, An O( √ VE) algorithm for finding maximum matching in general graphs, Proc. 21st Annual IEEE Symposium on Foundations of Computer Science (1980) 17-27. ⇒14110.1109/SFCS.1980.12Search in Google Scholar

[133] K. Mulmuley, U.V. Vazirani, V.V. Vazirani, Matching is as easy as matrix inversion, Combinatorica 7, 1 (1987) 105-114. ⇒14110.1007/BF02579206Search in Google Scholar

[134] V. Nikiforov, An analytic theory of extremal hypergraph problems, arXiv:1305.1073, 2013, 31 pages. ⇒142Search in Google Scholar

[135] F. Olejník, On total matching numbers and total covering numbers for k-uniform hypergraphs. Math. Slovaca 34, 3 (1984), 319-328. ⇒141Search in Google Scholar

[136] F. Olejník, On edge independence numbers and edge covering numbers of kuniform hypergraph, Math. Slovaca 39, 1 (1989) 21-26. ⇒138, 139, 140Search in Google Scholar

[137] L. özkahiya, M. E. Young, Anti-Ramsey number of matchings in hypergraphs, Discrete Math., 313, 20 (2013), 2359-2364. ⇒14110.1016/j.disc.2013.06.015Search in Google Scholar

[138] S. Pirzada, Hypertournaments-scores, losing scores, total scores and degrees. J. Combin. Math. Combin. Comput. 84 (2013) 99-112. ⇒139Search in Google Scholar

[139] S. Pirzada, G. Zhou, On k-hypertournament losing scores, Acta Univ. Sapientiae, Informatica 2, 1 (2010) 5-9. ⇒139Search in Google Scholar

[140] S. Pirzada, G. Zhou, A. Iványi, Score lists in multipartite hypertournaments, Acta Univ. Sapientiae, Informatica 2, 2 (2010) 184-193. ⇒139Search in Google Scholar

[141] K. Plociennik, Approximating independent set and coloring in random uniform hypergraphs. In: Mathematical Foundations of Computer Science (2008), Lecture Notes in Comput. Sci. 5162, Springer, Berlin, 2008, 539-550. ⇒14110.1007/978-3-540-85238-4_44Search in Google Scholar

[142] M. D. Plummer, Matching theory-a sampler: from Dénes König to the present, Discrete Math. 100 (1992) 172-219. ⇒14110.1016/0012-365X(92)90640-2Search in Google Scholar

[143] A. Pruchnewski, On the domination number of graphs, Discrete Math., 251, 1-3 (2002) 129-136. ⇒13710.1016/S0012-365X(01)00334-XSearch in Google Scholar

[144] J. Qian, Enumeration of unlabeled uniform hypergraphs, Electronic J. Combin 20, 1 (2013), P46, 10 pages ⇒13910.37236/2766Search in Google Scholar

[145] J. Qian, Enumeration of unlabeled uniform hypergraphs. Discrete Math. 326 (2014), 66-74. ⇒13910.1016/j.disc.2014.03.005Search in Google Scholar

[146] V. Rödl, A. Ruci´ski, M. Schacht, E. Szemerédi, A note on perfect matchings in uniform hypergraphs with large minimum collective degree, Comment. Math. Univ. Carolin. 49, 4 (2008) 633-636. ⇒141Search in Google Scholar

[147] V. Rödl, A. Ruciński, E. Szemerédi, Perfect matchings in uniform hypergraphs with large minimum degree, Europ. J. Combin. 27 (2006) 1333-1349. ⇒14110.1016/j.ejc.2006.05.008Search in Google Scholar

[148] V. Rödl, A. Ruciński, E. Szemerédi, Perfect matchings in large uniform hypergraphs with large minimum collective degree, J. Combin. Theory Ser. A 116, 3 (2009), 613-636. ⇒14110.1016/j.jcta.2008.10.002Search in Google Scholar

[149] S. Sakai, M. Mitsunori, K. Yamazaki, A note on greedy algorithms for the maximum weighted independent set problem. Discrete Appl. Math 126, 2-3 (2003) 313-322. ⇒13610.1016/S0166-218X(02)00205-6Search in Google Scholar

[150] S. M. Selkow, A probabilistic lower bound on the independence number of graphs. Discrete Math. 132 (1994) 363-365. ⇒134, 13510.1016/0012-365X(93)00102-BSearch in Google Scholar

[151] H. Shachnai, A. Srinivasan, Finding large independent sets in graphs and hypergraphs. SIAM J. Discrete Math. 18, 3 (2004/05) 488-500. ⇒14110.1137/S0895480102419731Search in Google Scholar

[152] J. Shearer, A note on the independence number of triangle-free graphs, Discrete Math. 46 (1983) 83-87. ⇒134, 136, 141, 14510.1016/0012-365X(83)90273-XSearch in Google Scholar

[153] J. Spencer, Turán’s theorem for k-graphs, Discrete Math. 2 (1972) 183-186. ⇒ 13610.1016/0012-365X(72)90084-2Search in Google Scholar

[154] E. Szymańska, The complexity of 2-coloring and strong coloring in uniform hypergraphs of high minimum degre, Discrete Math. Theor. Comput. Sci. 15, 3 (2013) 121-137. ⇒141, 14210.46298/dmtcs.596Search in Google Scholar

[155] R. E. Tarjan, A. E. Trojanowski, Finding a maximum independent set, SIAM J. Comput. 6, 3 (1977) 537-546. ⇒133, 138, 14110.1137/0206038Search in Google Scholar

[156] T. Thiele, A lower bound on the independence number of arbitrary hypergraphs, J. Graph Theory 30, 3 (1999) 213-221. ⇒13510.1002/(SICI)1097-0118(199903)30:3<213::AID-JGT6>3.0.CO;2-QSearch in Google Scholar

[157] A. Treglown, Y. Zhao, Exact minimum degree thresholds for perfect matchings in uniform hypergraphs, J. Combin. Theory Ser. A 119, 7 (2012) 1500-1522. ⇒141, 14210.1016/j.jcta.2012.04.006Search in Google Scholar

[158] A. Treglown, Y. Zhao, Exact minimum degree thresholds for perfect matchings in uniform hypergraphs II., J. Combin. Theory Ser. A 120, 7 (2013) 1463-1482. ⇒141, 14210.1016/j.jcta.2013.04.008Search in Google Scholar

[159] P. Turán, On the theory of graphs, Colloq. Math. 3 (1954) 19-30. ⇒133, 13410.4064/cm-3-1-19-30Search in Google Scholar

[160] Zs. Tuza, Extensions of Gallai’s graph covering theorems for uniform hypergraphs, J. Combin. Theory, Series B 52, 1 (1991) 92-96. ⇒139, 14210.1016/0095-8956(91)90094-ZSearch in Google Scholar

[161] V. V. Vazirani, A theory of alternating paths and blossoms for proving correctness of the O( √ VE) maximum matching algorithm, Combinatorica 14, 1 (1994) 71-109. ⇒13310.1007/BF01305952Search in Google Scholar

[162] V. V. Vazirani, An improved definition of blossoms and a simpler proof of the MV matching algorithm, arXiv:1210.4594, 2013, 32 pages. ⇒133Search in Google Scholar

[163] A. Vietri, The complexity of arc-colorings for directed hypergraphs, Discrete Appl. Math 143,1-3 (2004) 266-271. ⇒14010.1016/j.dam.2004.04.002Search in Google Scholar

[164] C. Wang, G. Zhou, Note on the degree sequences of k-hypertournaments, Note on the degree sequences of k-hypertournaments, Discrete Math. 308, 11 (2008) 2292-2296. ⇒139Search in Google Scholar

[165] V. Wei, A lower bound on the stability number of a simple graph, Bell Laboratories Technical Memorandum, 1981, No. 81-11217-9. ⇒134Search in Google Scholar

[166] E. W. Weisstein, Independent Edge Set. Downloaded 9 May 2014. ⇒133Search in Google Scholar

[167] Wikipedia, Independent Set. Downloaded 9 May 2014. ⇒133, 138Search in Google Scholar

[168] R. Yuster, Finding and counting cliques and independent sets in r-uniform hypergraphs. Inf. Processing Letters 99, 4 (2006) 130-134. ⇒14110.1016/j.ipl.2006.04.005Search in Google Scholar

[169] R. Yuster, Maximum matching in regular and almost regular graphs, Algorithmica 66, 1 (2013) 87-92. ⇒141, 14210.1007/s00453-012-9625-7Search in Google Scholar

[170] G. Zhou, Y. Li, Independence numbers of hypergraphs with sparse neighborhoods, Europ. J. Combin. 25, 3 (2004) 355-362. ⇒134, 140, 141, 14210.1016/j.ejc.2003.09.008Search in Google Scholar

[171] G. Zhou, S. Pirzada, Degree sequence of oriented k-hypergraphs, J. Appl. Math. Comput. 27, 1-2 (2008) 149158. ⇒13910.1007/s12190-008-0047-2Search in Google Scholar

[172] G. Zhou, T. Yao, K. Zhang, On score sequences of k-hypertournaments, Europ. J. Combin. 21, 8 (2000) 993-1000. ⇒13910.1006/eujc.2000.0393Search in Google Scholar