Revista de la
Unión Matemática Argentina
Clique coloring EPT graphs on bounded degree trees
Pablo De Caria, María Pía Mazzoleni, and María Guadalupe Payo Vidal

Volume 68, no. 1 (2025), pp. 79–101    

Published online (final version): March 29, 2025

https://doi.org/10.33044/revuma.3511

Download PDF

Abstract

The edge-intersection graph of a family of paths on a host tree is called an EPT graph. When the host tree has maximum degree $h$, we say that the graph is $[h,2,2]$. If the host tree also satisfies being a star, we have the corresponding classes of EPT-star and $[h,2,2]$-star graphs. In this paper, we prove that $[4,2,2]$-star graphs are $2$-clique colorable, we find other classes of EPT-star graphs that are also $2$-clique colorable, and we study the values of $h$ such that the class $[h,2,2]$-star is $3$-clique colorable. If a graph belongs to $[4,2,2]$ or $[5,2,2]$, we prove that it is $3$-clique colorable, even when the host tree is not a star. Moreover, we study some restrictions on the host trees to obtain subclasses that are $2$-clique colorable.

References

  1. L. Alcón, M. Gutierrez, and M. P. Mazzoleni, EPT graphs on bounded degree trees, Mat. Contemp. 42 (2012), 1–7.  DOI  MR  Zbl
  2. T. Andreae, M. Schughart, and Z. Tuza, Clique-transversal sets of line graphs and complements of line graphs, Discrete Math. 88 no. 1 (1991), 11–20.  DOI  MR  Zbl
  3. G. Bacsó, S. Gravier, A. Gyárfás, M. Preissmann, and A. Sebő, Coloring the maximal cliques of graphs, SIAM J. Discrete Math. 17 no. 3 (2004), 361–376.  DOI  MR  Zbl
  4. G. Bacsó, Z. Ryjáček, and Z. Tuza, Coloring the cliques of line graphs, Discrete Math. 340 no. 11 (2017), 2641–2649.  DOI  MR  Zbl
  5. B. Beauquier, J.-C. Bermond, L. Gargano, P. Hell, S. Pérennes, and U. Vaccaro, Graph problems arising from wavelength-routing in all-optical networks, in Proceedings of the Second Workshop on Optics and Computer Science, IPPS '97, 1997, also available as INRIA Rapport de recherche no. 3165, https://inria.hal.science/inria-00073523.
  6. J. A. Bondy and U. S. R. Murty, Graph theory, Graduate Texts in Mathematics 244, Springer, New York, 2008.  MR  Zbl
  7. C. N. Campos, S. Dantas, and C. P. de Mello, Colouring clique-hypergraphs of circulant graphs, in The IV Latin-American Algorithms, Graphs, and Optimization Symposium, Electron. Notes Discrete Math. 30, Elsevier, Amsterdam, 2008, pp. 189–194.  DOI  MR  Zbl
  8. M. R. Cerioli and A. L. Korenchendler, Clique-coloring circular-arc graphs, in LAGOS'09—V Latin-American Algorithms, Graphs and Optimization Symposium, Electron. Notes Discrete Math. 35, Elsevier, Amsterdam, 2009, pp. 287–292.  DOI  MR  Zbl
  9. M. R. Cerioli and P. Petito, Clique-coloring UE and UEH graphs, in The IV Latin-American Algorithms, Graphs, and Optimization Symposium, Electron. Notes Discrete Math. 30, Elsevier, Amsterdam, 2008, pp. 201–206.  DOI  MR  Zbl
  10. P. Charbit, I. Penev, S. Thomassé, and N. Trotignon, Perfect graphs of arbitrarily large clique-chromatic number, J. Combin. Theory Ser. B 116 (2016), 456–464.  DOI  MR  Zbl
  11. G. A. Dirac, On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg 25 (1961), 71–76.  DOI  MR  Zbl
  12. D. Duffus, H. A. Kierstead, and W. T. Trotter, Fibres and ordered set coloring, J. Combin. Theory Ser. A 58 no. 1 (1991), 158–164.  DOI  MR  Zbl
  13. D. Duffus, B. Sands, N. Sauer, and R. E. Woodrow, Two-colouring all two-element maximal antichains, J. Combin. Theory Ser. A 57 no. 1 (1991), 109–116.  DOI  MR  Zbl
  14. T. Erlebach and K. Jansen, Scheduling of virtual connections in fast networks, in Proceedings of the 4th Workshop on Parallel Systems and Algorithms PASA '96, World Scientific, Singapore, 1997, pp. 13–32.  DOI
  15. T. Erlebach, A. Pagourtzis, K. Potika, and S. Stefanakos, Resource allocation problems in multifiber WDM tree networks, in Graph-theoretic concepts in computer science (WG 2003), Lecture Notes in Comput. Sci. 2880, Springer, Berlin, 2003, pp. 218–229.  DOI  MR  Zbl
  16. M. C. Golumbic and R. E. Jamison, Edge and vertex intersection of paths in a tree, Discrete Math. 55 no. 2 (1985), 151–159.  DOI  MR  Zbl
  17. M. C. Golumbic and R. E. Jamison, The edge intersection graphs of paths in a tree, J. Combin. Theory Ser. B 38 no. 1 (1985), 8–22.  DOI  MR  Zbl
  18. M. C. Golumbic, M. Lipshteyn, and M. Stern, Representing edge intersection graphs of paths on degree 4 trees, Discrete Math. 308 no. 8 (2008), 1381–1387.  DOI  MR  Zbl
  19. R. E. Jamison and H. M. Mulder, Constant tolerance intersection graphs of subtrees of a tree, Discrete Math. 290 no. 1 (2005), 27–46.  DOI  MR  Zbl
  20. J. Kratochvíl and Z. Tuza, On the complexity of bicoloring clique hypergraphs of graphs, J. Algorithms 45 no. 1 (2002), 40–54.  DOI  MR  Zbl
  21. T. A. McKee and F. R. McMorris, Topics in intersection graph theory, SIAM Monogr. Discrete Math. Appl., Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1999.  DOI  MR  Zbl
  22. J. Mycielski, Sur le coloriage des graphs, Colloq. Math. 3 (1955), 161–162.  DOI  MR  Zbl
  23. H. Poon, Coloring clique hypergraphs, Master's thesis, West Virginia University, 2000.  DOI