Asia Mathematika

An International Journal. ISSN: 2457-0834 (online)

Volume 3, Issue 1, April 2019, Pages: 33-40

Computation of First-Fit Coloring of Graphs

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.


▷Download pdf


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.

Visitors count

Join us