Clique coloring EPT graphs on bounded degree trees

• Pablo De Caria ^[1] ; María Pía Mazzoleni ^[1] ; María Guadalupe Payo Vidal ^[1]
  1. [1] CONICET and CMaPL (Centro de Matem´atica de La Plata), Argentina
• Localización: Revista de la Unión Matemática Argentina, ISSN 0041-6932, ISSN-e 1669-9637, Vol. 68, Nº. 1, 2025, págs. 79-101
• Idioma: inglés
• DOI: 10.33044/revuma.3511
• Enlaces
  • Texto completo
• Resumen

  • 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 hh, we say that the graph is [h,2,2][h,2,2]. If the host tree also satisfies being a star, we have the corresponding classes of EPT-star and [h,2,2][h,2,2]-star graphs. In this paper, we prove that [4,2,2][4,2,2]-star graphs are 22-clique colorable, we find other classes of EPT-star graphs that are also 22-clique colorable, and we study the values of hh such that the class [h,2,2][h,2,2]-star is 33-clique colorable. If a graph belongs to [4,2,2][4,2,2] or [5,2,2][5,2,2], we prove that it is 33-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 22-cl

• Referencias bibliográficas
  • L. Alcon´ , M. Gutierrez, and M. P. Mazzoleni, EPT graphs on bounded degree trees, Mat. Contemp. 42 (2012), 1–7. DOI MR Zbl
  • T. Andreae, M. Schughart, and Z. Tuza, Clique-transversal sets of line graphs and complements of line graphs, Discrete Math. 88 no. 1 (1991),...
  • G. Bacso´, S. Gravier, A. Gyarf ´ as´ , M. Preissmann, and A. Sebo˝, Coloring the maximal cliques of graphs, SIAM J. Discrete Math. 17 no....
  • G. Bacso´, Z. Ryja´cek ˇ , and Z. Tuza, Coloring the cliques of line graphs, Discrete Math. 340 no. 11 (2017), 2641–2649. DOI MR Zbl
  • B. Beauquier, J.-C. Bermond, L. Gargano, P. Hell, S. Perennes ´ , and U. Vaccaro, Graph problems arising from wavelength-routing in all-optical...
  • J. A. Bondy and U. S. R. Murty, Graph theory, Graduate Texts in Mathematics 244, Springer, New York, 2008. MR Zbl
  • C. N. Campos, S. Dantas, and C. P. de Mello, Colouring clique-hypergraphs of circulant graphs, in The IV Latin-American Algorithms, Graphs,...
  • M. R. Cerioli and A. L. Korenchendler, Clique-coloring circular-arc graphs, in LAGOS’09—V Latin-American Algorithms, Graphs and Optimization...
  • M. R. Cerioli and P. Petito, Clique-coloring UE and UEH graphs, in The IV Latin-American Algorithms, Graphs, and Optimization Symposium, Electron....
  • P. Charbit, I. Penev, S. Thomasse´, and N. Trotignon, Perfect graphs of arbitrarily large clique-chromatic number, J. Combin. Theory Ser....
  • G. A. Dirac, On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg 25 (1961), 71–76. DOI MR Zbl
  • 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...
  • 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),...
  • T. Erlebach and K. Jansen, Scheduling of virtual connections in fast networks, in Proceedings of the 4th Workshop on Parallel Systems and...
  • T. Erlebach, A. Pagourtzis, K. Potika, and S. Stefanakos, Resource allocation problems in multifiber WDM tree networks, in Graph-theoretic...
  • 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
  • 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...
  • M. C. Golumbic, M. Lipshteyn, and M. Stern, Representing edge intersection graphs of paths on degree 4 trees, Discrete Math. 308 no. 8 (2008),...
  • 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...
  • 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
  • T. A. McKee and F. R. McMorris, Topics in intersection graph theory, SIAM Monogr. Discrete Math. Appl., Society for Industrial and Applied...
  • J. Mycielski, Sur le coloriage des graphs, Colloq. Math. 3 (1955), 161–162. DOI MR Zbl
  • H. Poon, Coloring clique hypergraphs, Master’s thesis, West Virginia University, 2000. DOI