Date Log
CHROMATIC NUMBER, CHROMATIC POLYNOMIALS AND CHROMATIC UNIQUENESS OF SPLIT GRAPHS
Corresponding Author(s) : Le Xuan Hung
UED Journal of Social Sciences, Humanities and Education,
Vol. 4 No. 4 (2014): UED JOURNAL OF SOCIAL SCIENCES, HUMANITIES AND EDUCATION
Abstract
The notion of split graphs was introduced in 1977 by S. Foldes and P.L. Hammer. These graphs have been extensively studied because they are in connection with combinatorial problems and computer science such as packing and knapsack problems, the matroid theory, Boolean function, the analysis of parallel processes of computer programs and the task allocation of distributed systems… One of the fundamental matters in graph theory is the graph coloring, especially the determination of chromatic number, chromatic polynomials, and the uniqueness of graph coloring. This paper determines the chromatic number, chromatic polynomials and chromatical uniqueness of split graphs.
Keywords
Download Citation
Endnote/Zotero/Mendeley (RIS)BibTeX
-
[1] M. Behazad and G. Chartrand (1971), Introduction to the Theory of graphs, Allyn and Bacon, Boston.
[2] G. D. Birkhoff (1912), A determinant formula for the number of ways of coloring a map, Annals of Math, 14 (2), 42 -46.
[3] J. A. Bondy and U. S. R. Murty (1976), Graph theory with applications, MacMillan.
[4] B.-L. Chen, H.-L Fu, M.T. Ko (1995), Total chromatic number and chromatic index of split graphs, J. Combin. Math. Combin. Comput. 17, 137 – 146.
[5] V. Chvatal and P.L. Hammer (1977), Aggregation of inequalities in integer programming, Ann. Discrete Math. 1, pp. 145 – 162.
[6] S. Foldes and P.L. Hammer (1977), Split graphs, In: Proceeding of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State University, Baton Rouge, LA, 1977), Congressus Numerantium, vol. XIX, Utilitas Mathematics, Winnipeg, Man., pp. 311 – 315.
[7] S. Foldes and P.L. Hammer (1978), On a class of matroid-producing graphs, In: Combinatorics (Proceeding of the Filth Hungarian Colloquium, Kesrthely, 1976), vol. 1, Colloquium Mathematical Society, Jano’s Bolyai, vol. 18, North-Holland, Amsterdam, New York, pp. 331 - 352.
[8] P. B. Henderson and Y. Zalcstein (1977), A graph-theoretic characterization of the class of synchroniring primitive, SIAM J. Comput. 6, 88-108.
[9] A. Hesham H. And El-R. Hesham (1993), Task allocation in distributed systems: a split graph model, J. Combin. Math. Combin. Comput. 14, 15-32.
[10] K. M. Koh and K. L. Teo (1990), The search for chromatically unique graphs, Graphs Combin. 6, 259-285.
[11] K. M. Koh and K. L. Teo (1997), The search for chromatically unique graphs II, Discrete Math. 172, 59-78.
[12] U. N. Peled (1975), Regular Boolean functions and their polytope, Chapter VI, PH. D. Thesis, Univ. Of Waterloo, Dept. Combin. And Optimization.
[13] R. C. Read (1968), An introduction to chromatic polynomials, J. Combin. Theory 4, 52-71.
[14] R. C. Read (1987), Connectivity and chromatic uniqueness, Ars Combin. 23, 209-218.