ON $\psi$- CRITICALITY OF SOME RANDOM GRAPHS

Year 2026, Volume: 16 Issue: 1, 123 - 133, 08.01.2026

S. Kokiladevi Yegnanarayanan Venkataraman Rajermani Thinakaran

Abstract

A vertex colouring g of a graph G is said to be pseudocomplete if for any two distinct colours i, j there exists at least one edge $e = (u, v) \in E(G)$ such that $g(u) = i $ and $g(v) = j$. The maximum number of colors used in a pseudocomplete coloring is called the pseudoachromatic number $\psi(G)$ of G. A Graph G is called vertex $\psi$-critical if $ \omega(G) = 2 \psi(G) - \vert V(G)\vert$. If $P^*$ is a criticality property with respect to $\psi$ then we have obtained some interesting results related to the random graphs as process innovation. We also proved that there is positive probability for the existence of a large collection of family of graphs that are not critical. We also listed a number of open problems.

Keywords

Random Graphs , Colouring , Pseudoachromatic Number , Vertex $\psi $-Critical Graphs

References

• Balasubramanian, R., Raman, V. and Yegnanarayanan, V., (2003), On the pseudoachromatic number of join of graphs, J. Computer Math., 80, pp. 1131–1137.
• Bhave, V. N., (1979), On the pseudoachromatic number of a graph, Fund. Math., 102(3), pp. 159–164.
• Bodlaender, H. L., (1989), Achromatic number is np-complete for cographs and interval graphs, Inform, Process. Lett., 31(3), pp. 135–138.
• Bollobas, B. and Bela, (1998), Modern graph theory, Graduate Texts in Mathematics, Springer-Verlag, New York, 184.
• Bollobas, B., Catlin, P. A. and Erdos, P., (1980), Hadwigers conjecture is true for almost all graphs, Europ. J. Combin., 1, pp. 195–199.
• Bollobas, B., Reed, B. and Thomason, A., (1993), An extremal function for the achromatic number, Graph structure theory, 147, pp. 161–165.
• Brown, J. I., (1992), A vertex critical graph without critical edges, Discrete Mathematics, 102(1), pp. 99–101.
• Cairnie, N. and Edwards, K. J., (1997), Some results on the achromatic number, J. Graph Theory, 23(3), pp. 129–136.
• Cairnie, N. and Edwards, K. J., (1998), The achromatic number of bounded degree trees, Discrete Math., 188, pp. 87–97.
• Chandran, L., Sunil, Sivadasan and Naveen (2007), On the hadwiger’s conjecture for graph products, Discrete Math., 307(2), pp. 266–273.
• Chen, J., Huang, X., Kanj, I. and Xia, G., (2006), Strong computational lower bounds via parametrized complexity, Journal of computer and system sciences, pp. 1346–1367.
• Chen, J., Kanj, I. A., Meng, J., Xia, G. and Zhang, F., (2009), On the pseudoachromatic number problem, Theoretical Computer Science, 410, pp. 818–829.
• Edwards, K. J., (1997), The harmonious chromatic number and the achromatic number, Surveys in Combinatorics, Cambridge University Press, pp. 13–47.
• Edwards, K. J., (2000), Achromatic number versus pseudo achromatic number: A counterexample to a conjecture of hedetniemi, Discrete Math., 219(1–3), pp. 271–274.
• Edwards, K. J. and McDiarmid, C. J. H., (1995), The complexity of harmonious coloring for trees, Disc. Appl. Math., 57, pp. 133–144.
• Farber, M., Hahn, G., Hell, P. and Miller, D., (1986), Concerning the achromatic number of graphs, J. Combinat. Theory Ser. B, 40(1), pp. 21–39.
• Geller, D. and Kronk, H., (1974), Further results on the achromatic number, Fund. Math., pp. 285–290.
• Goncalves, D., Montassier, M. and Pinlou, A., (2014), Entropy compression method applied to graph colorings, ArXiv 1406.4380.
• Gupta, R. P., (1968), Bounds on the chromatic and achromatic numbers of complementary graphs, Recent Progress in Combinatorics, pp. 229–235.
• Gyarf, A., (1987), Problems from the world surrounding perfect graphs, Applicationes Mathematicae, 19, pp. 413–444.
• Hedetniemi, S., (1998), Open problems in combinatorial optimization.
• Jensen, T. R., (2002), Dense critical and vertex-critical graphs, Discrete Mathematics, 258, pp. 63–84.
• Joret, Gwenael, Wood and David, R., (2011), Complete graph minors and the graph minor structure theorem.
• Kortsarz, G. and Krauthgamer, R., (2000), On the approximation of the achromatic number, SIAM Journal of Discrete Math., 14(3), pp. 408–422.
• Kortsarz, G. and Shende, S., (2003), Approximating the achromatic number problem on bipartite graphs, 11th European Symposium on Algorithms (Budapest, 2003), Vol. 2832, Lecture Notes in Computer Science, Springer, Berlin, pp. 385–396.
• Kostochka, A. V., (1982), The minimum hadwiger number for graphs with a given mean degree of vertices, Metody Diskret, Analiz., 38, pp. 37–58.
• Kostochka, A. and Yancey, M., (2014), Ore’s conjecture on color-critical graphs is almost true, J. Comb. Theory, Ser. B, 109, pp. 73–101.
• Lattanzio, J. J., (2002), A note on a conjecture of dirac, Discrete Mathematics, 258(1–3), pp. 323–300.
• Liu, M. and Liu, B., (2011), On pseudoachromatic number of graphs, Southeast Asian Bulletin Of Mathematics, 35, pp. 431–438.
• MacGillivray, Gary, A. R., (2001), The achromatic number of the union of paths, Discrete Math., 231(1–3), pp. 331–335.
• McDiarmid, C. J. H., (1982), Achromatic numbers of random graphs, Mathematical Proceedings of Cambridge Philosophical Society, 92, pp. 21–28.
• Michael, M. and Reed, B., (1995), A critical point of random graphs with a given degree sequence, Random Structures and Algorithms, 6, pp. 161–179.
• Michael, M. and Reed, B., (1998), The size of the giant component of a random graph with a given degree sequence, Combinatorics, Probability and Computing, 7, pp. 295–305.
• Pavol, H. and Donald, M. J., (1976), Graph with given achromatic number, Discrete Math., 16(3), pp. 195–207.
• Postle, L., (2012), 5-List-Coloring Graphs on Surfaces, PhD thesis, Georgia Institute of Technology.
• Reinhard, D., (2000), Graph theory, Graduate Texts in Mathematics, second edn, Vol. 173, Springer-Verlag, New York.
• Robertson, N., Seymour, P. D. and Thomas, R., (1993), Hadwiger’s conjecture for k6-free graphs, Combinatorica, 13(3), pp. 279–261.
• Robertson, N. and Seymour, P. D., (2004), Graph minors. XX. Wagner’s conjecture. J. Comb. Theory Ser. B. 92, pp. 325–357.
• Robertson, N. and Seymour, P. D., (1995), Graph minors. XIII. The disjoint path problem. J. Comb. Theory Ser. B. 63, pp. 65–110.
• Archdeacon, D., (1987), A note on defective colorings of graphs in surfaces, J. Graph Theory, 11, pp. 517–519.
• Edwards, K., Kang, D. Y., Kim, J., Oum, S. and Seymour, P., (2015), A relative of Hadwiger’s conjective, SIAM J. D iscrete Math. 29, pp. 2385–2388.
• Roichman, Y., (1990), The achromatic number of trees, grids and cubes, PhD thesis, Hebrew University.
• Sampathkumar, E. and Bhave, V. N., (1976), Partition graphs and coloring numbers of a graph, Discrete Math., 16(1), pp. 57–60.
• Thomassen, C., (1997), Color-critical graphs on a fixed surface, J. Combin. Theory, Ser. B. 70, pp. 67–100.
• Vetrivel, G., Mullai, M. and Rajchakit, G., (2024), Product operations on pythagorean co-neutrosophic graphs and its application, Neutrosophic Sets and Systems, 72, pp. 357–380.
• Wood, R. D., (2007), On the maximum number of cliques in a graph, Graphs Combin., 23(3), pp. 337–352.
• Wood, R. D., (2011), Clique minors in cartesian products of graphs, pp. 1–56.
• Yegnanarayanan, V., (1998), Concerning pseudocomplete partitionig of graphs, Pure and Applied Mathematika Sciences, 48(1–2), pp. 23–31.
• Yegnanarayanan, V., (1999), Some external graph problems of Nordhaus-Gaddum class, Bulletin of Allahabad Mathematical Society, 14, pp. 147–158.
• Yegnanarayanan, V., (2000), The pseudoachromatic number of a graph, Southeast Asian Bull. Math., 24(1), pp. 129–136.
• Yegnanarayanan, V., (2001), Graph colouring and partitions, Theoretical Computer Science, 263, pp. 59–74.
• Yegnanarayanan, V., (2002), On pseudocomplete coloring of graphs, Utilitas Mathematica, 62.
• Yegnanarayanan, V., (2009), On computational complexity of pseudoachromatic number of a graph, Utilitas Mathematica, 78, pp. 159–163.
• Yegnanarayanan, V., Balakrishnan, R. and Sampath Kumar, R., (1998), Extremal graphs in some graph colouring problems, Discrete Mathematics, 186, pp. 15–24.
• Yegnanarayanan, V., Balakrishnan, R. and Sampath Kumar, R., (2000), A note on the existence of graphs with prescribed colouring parameters, Discrete Mathematics, 216(1–3), pp. 293–297.
• Yegnanarayanan, V. and Thiripurasundari, P. K., (2009), On some graph operations and related applications, Electronic Notes in Discrete Mathematics, 33, pp. 123–130.