Clique coloring EPT graphs on bounded degree trees
DOI:
https://doi.org/10.33044/revuma.3511Abstract
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.
Downloads
References
L. Alcón, 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), 11–20. DOI MR Zbl
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
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
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.
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, and Optimization Symposium, Electron. Notes Discrete Math. 30, Elsevier, Amsterdam, 2008, pp. 189–194. DOI MR Zbl
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
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
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
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 Zbl
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
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
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
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 Zbl
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
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
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 Mathematics (SIAM), Philadelphia, PA, 1999. DOI MR Zbl
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
Downloads
Published
Issue
Section
License
Copyright (c) 2025 Pablo De Caria, María Pía Mazzoleni, María Guadalupe Payo Vidal
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal. The Journal may retract the paper after publication if clear evidence is found that the findings are unreliable as a result of misconduct or honest error.
