Volume 3, Issue 1, April 2019, Pages: 33-40
V. Yegnanarayanan
School of Humanities and Sciences, SASTRA University, Thanjavur-613401, TN, India
The first-fit chromatic number of a graph is the maximum possible number of colors used in a first fit coloring of the graph. In this paper, we compute the first-fit chromatic number for a special class of bipartite graphs. Further we give a crisp description on the computational aspects of the first fit chromatic number and indicate the scope for further applications. We also raise some open problems.
Graph, coloring, chromatic number, First-Fit Chromatic Number.
1. Adamy U, Erlebach T. Online coloring of intervals with bandwidth, In Klaus Jansen and Roberto Solis-Oba, editors, First International Workshop on Approximation and Online Algorithms, (WAOA 2003), volume 2909 of Lecture Notes in Computer Science, 2004; 1-12.
2. Ali Mansouri, Mohamed Salim Bouhlel. A Linear Algorithm for the Grundy Number of A Tree. International Journal of Computer Science & Information Technology (IJCSIT) 2014; 6(1): 155-160.
3. Christen CA, Selkow SM. Some perfect coloring properties of graphs. Journal of Combinatorial Theory, Series B 1979; 27: 49-59.
4. Chrobak M, Slusarek M. On some packing problems related to dynamic storage allocation. Informatique theorique et Applications/Theoretical Informatics and Applications 1988; 22(4): 487-499.
5. Edouard Bonnet, Florent Foucaud, Eun Jung Kim, Florian Sikora. Complexity of Grundy coloring and its variants, arXiv : 1407.5336v/[CS.DS] 2014; 1-18.
6. Erdos P, Hedetneiemi ST, Laskar RC, Prins CE. On the quality of the partial Grundy and upper ochromatic numbers of graphs. Discrete Mathematics 2003; (272): 53-64.
7. Fabri J. Automatic storage optimization. ACM SIGPLAN Notices: Proceedings of the ACM SIGPLAN ’79 on Compiler Construction 1979; 14(8): 83-91.
8. Feige U, Killian J. Zero knowledge and the chromatic number. Journal of Computer and System Sciences 1998; 57(2): 187-199.
9. Ershov AP. Alpha - an automatic programming system of high efficiency. Journal of the ACM 1966; 13(1): 17-24.
10. Govindarajan R, Rengarajan S. Buffer Allocation in Regular Dataflow Networks: An Approach Based on Coloring Circular-Arc Graphs. Proc. Third Int.Conf. on High Performance computing (HiPC’96) 1996; 419. ISBN:0-8186- 7557-8, IEEE Computer Society, Washington, DC, USA. 1996.
11. Grundy PM. Mathematics and games. Eureka 1939; 2: 6-8.
12. Irani S. Coloring inductive graphs on-line. Algorithmica 1994; 11(1): 53-72.
13. Kierstead HA, Trotter WT. An extremal problem in recursive combinatorics. Congressus Numerantium 1981; 33: 143-153.
14. Kierstead HA. The linearity of first-fit coloring of interval graphs. SIAM Journal on Discrete Mathematics 1988; (1): 526-530.
15. Kierstead HA, Qin J. Coloring of interval graphs with First Fit. Discrete Mathematics 1995; (144): 47-57.
16. Paul Wilson R, Mark Johnstone S, Michael Neely, David Bo les. Dynamic storage allocation : A survey and critical review. In Proceedings of the International Workshop on Memory Management (IWMM) 1995; 1-116.
17. Pemmaraju S, Raman R, Varadarajan K. Buffer minimization using max-coloring. Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans. Louisiana 2004; 562-571.
18. Woodall DR. Problem No. 4. Proceedings of the British Combinatorial Conference, 1973, London Mathematical Society, Lecture Note Series. 13, Cambridge University Press, 1974.
19. Yon-Te Tsai, Yaw-Ling Lin, Hsu FR. The on-line first fit algorithm for radio frequency assignment problems. Information Processing Letters 2002; 84: 195-199.
20. Yegnanarayanan V, Balakrishnan R, Sampathkumar R. On the existence of graphs with prescribed coloring parameters. Discrete Mathematics 2000; (216): 293-297.
21. Zaker M. Results on the Grundy chromatic number of graphs. Discrete Mathematics 2002; 306(23); 3166-3173.
