ON $\psi$- CRITICALITY OF SOME RANDOM GRAPHS

S. Kokiladevi; Yegnanarayanan Venkataraman; Rajermani Thinakaran

ON $\psi$- CRITICALITY OF SOME RANDOM GRAPHS

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

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.

Details

Primary Language

English

Subjects

Combinatorics and Discrete Mathematics (Excl. Physical Combinatorics)

Journal Section

Research Article

Authors

S. Kokiladevi This is me
0009-0002-1909-7482
India

Yegnanarayanan Venkataraman ^* This is me
0000-0001-9798-8825
India

Rajermani Thinakaran This is me
0000-0002-9525-8471
Malaysia

Publication Date

January 8, 2026

Submission Date

December 17, 2024

Acceptance Date

February 21, 2025

Published in Issue

Year 2026 Volume: 16 Number: 1

IZ

https://izlik.org/JA84TR45SC

Cite

RIS / Bibtex

APA

Kokiladevi, S., Venkataraman, Y., & Thinakaran, R. (2026). ON $\psi$- CRITICALITY OF SOME RANDOM GRAPHS. TWMS Journal of Applied and Engineering Mathematics, 16(1), 123-133. https://izlik.org/JA84TR45SC

AMA

1.Kokiladevi S, Venkataraman Y, Thinakaran R. ON $\psi$- CRITICALITY OF SOME RANDOM GRAPHS. JAEM. 2026;16(1):123-133. https://izlik.org/JA84TR45SC

Chicago

Kokiladevi, S., Yegnanarayanan Venkataraman, and Rajermani Thinakaran. 2026. “ON $\psi$- CRITICALITY OF SOME RANDOM GRAPHS”. TWMS Journal of Applied and Engineering Mathematics 16 (1): 123-33. https://izlik.org/JA84TR45SC.

EndNote

Kokiladevi S, Venkataraman Y, Thinakaran R (January 1, 2026) ON $\psi$- CRITICALITY OF SOME RANDOM GRAPHS. TWMS Journal of Applied and Engineering Mathematics 16 1 123–133.

IEEE

[1]S. Kokiladevi, Y. Venkataraman, and R. Thinakaran, “ON $\psi$- CRITICALITY OF SOME RANDOM GRAPHS”, JAEM, vol. 16, no. 1, pp. 123–133, Jan. 2026, [Online]. Available: https://izlik.org/JA84TR45SC

ISNAD

Kokiladevi, S. - Venkataraman, Yegnanarayanan - Thinakaran, Rajermani. “ON $\psi$- CRITICALITY OF SOME RANDOM GRAPHS”. TWMS Journal of Applied and Engineering Mathematics 16/1 (January 1, 2026): 123-133. https://izlik.org/JA84TR45SC.

JAMA

1.Kokiladevi S, Venkataraman Y, Thinakaran R. ON $\psi$- CRITICALITY OF SOME RANDOM GRAPHS. JAEM. 2026;16:123–133.

MLA

Kokiladevi, S., et al. “ON $\psi$- CRITICALITY OF SOME RANDOM GRAPHS”. TWMS Journal of Applied and Engineering Mathematics, vol. 16, no. 1, Jan. 2026, pp. 123-3, https://izlik.org/JA84TR45SC.

Vancouver

1.S. Kokiladevi, Yegnanarayanan Venkataraman, Rajermani Thinakaran. ON $\psi$- CRITICALITY OF SOME RANDOM GRAPHS. JAEM [Internet]. 2026 Jan. 1;16(1):123-3. Available from: https://izlik.org/JA84TR45SC