×

Advances on defective parameters in graphs. (English) Zbl 1387.05077

Summary: We consider the generalization of Ramsey numbers to the defective framework using \(k\)-dense and \(k\)-sparse sets. We construct the first tableaux for defective Ramsey numbers with exact values whenever it is known, and lower and upper bounds otherwise. In light of defective Ramsey numbers, we consider the defective cocoloring problem which consists of partitioning the vertex set of a given graph into \(k\)-sparse and \(k\)-dense sets. By the help of efficient graph generation methods, we show that \(c_0(4)=12\), \(c_1(3)=12\) and \(c_2(2)=10\) where \(c_k(m)\) is the maximum order \(n\) such that all \(n\)-graphs can be \(k\)-defectively cocolored using at most \(m\) colors. We also give the numbers of \(k\)-defective \(m\)-cocritical graphs of order \(n\) (until \(n=10\)) for different levels of defectiveness and \(m=2,3\) and \(4\).

MSC:

05C15 Coloring of graphs and hypergraphs
05C55 Generalized Ramsey theory
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Software:

Triangleramsey
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ekim, T.; Gimbel, J., Some defective parameters in graphs, Graphs Combin., 29, 2, 213-224 (2013) · Zbl 1263.05028
[2] Radziszowski., S., Small Ramsey numbers, Electron. J. Combin. (1994-2011), Dynamic Surveys DS1 · Zbl 0953.05048
[4] Cowen, L.; Goddard, W.; Jesurum, E., Defective coloring revisited, J. Graph Theory, 24, 205-219 (1997) · Zbl 0877.05019
[5] Cockayne, E. J.; Mynhardt, C. M., On 1-dependent ramsey numbers for graphs, Discuss. Math. Graph Theory, 19, 1, 93-110 (1999) · Zbl 0932.05061
[7] Brandt, S.; Brinkmann, G.; Harmuth, T., All ramsey numbers \(r(K_3; G)\) for connected graphs of order 9, Electron. J. Combin., 5 (1998) · Zbl 0885.05088
[8] Brinkmann, G.; Goedgebeur, J.; Schlage-Puchta, J.-C., Ramsey numbers \(r(K_3, G)\) for graphs of order 10, Electron. J. Combin., 19 (2012) · Zbl 1266.05086
[9] Lesniak, L.; Straight, J., The cochromatic number of a graph, Ars Combin., 3, 39-45 (1977) · Zbl 0394.05020
[10] Straight, H. J., Extremal problems concerning the cochromatic number of a graph, J. Indian Math. Soc. (N.S.), 44, 137-142 (1980) · Zbl 0614.05027
[11] Erdös, P.; Gimbel, J.; Kratsch, D., Some extremal results in cochromatic and dichromatic theory, J. Graph Theory, 15, 579-585 (1991) · Zbl 0743.05047
[12] Gimbel, J.; Kratsch, D.; Stewart, L., On cocolourings and cochromatic numbers of graphs, Discrete Appl. Math., 48, 111-127 (1994) · Zbl 0795.05052
[13] Jørgensen, L. K., Critical 3-cochromatic graphs, Graphs Combin., 11, 263-266 (1995) · Zbl 0836.05027
[14] Demange, M.; Ekim, T.; de Werra, D., A tutorial on the use of graph coloring models for some problems in robotics, European J. Oper. Res., 192, 41-55 (2009) · Zbl 1198.05045
[15] Ekim, T.; Gimbel, J., Partitioning graphs into complete and empty graphs, Discrete Math., 309, 5849-5856 (2009) · Zbl 1186.05095
[16] Demange, M.; Ekim, T.; de Werra, D., Partitioning cographs into cliques and stable sets, Discrete Optim., 2, 145-153 (2005) · Zbl 1136.05315
[19] Belmonte, R.; Heggernes, P.; van’t Hof, P.; Saei, R., Ramsey numbers for line graphs and perfect graphs, (COCOON 2012. COCOON 2012, Lecture Notes in Computer Science, vol. 7434 (2012)), 204-215 · Zbl 1365.05190
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.