×

The edge intersection graphs of paths in a tree. (English) Zbl 0537.05063

We investigate the class of edge intersection graphs of a collection of paths in a tree (EPT graphs) where two paths edge intersect if they share an edge. The cliques of an EPT graph are characterized and shown to have strong Helly number 4. From this we demonstrate that one can find a maximum clique of an EPT graph in polynomial time. We show that the strong perfect graph conjecture holds for EPT graphs. Further complexity results follow from the observation that every line graph is an EPT graph. The class of EPT graphs is equivalent to the class of fundamental cycle graphs.

MSC:

05C99 Graph theory
05C05 Trees
68W99 Algorithms in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arjomandi, E., An efficient algorithm for coloring the edges of a graph with Δ + 1 colors, INFOR, 20, 82-101 (1982) · Zbl 0521.05030
[2] Berge, C., (Graphs and Hypergraphs (1973), North-Holland: North-Holland Amsterdam) · Zbl 0483.05029
[3] Buckingham, M. A.; Golumbic, M. C., Recent results on the strong perfect graph conjecture, Ann. Discrete Math., 20, 75-82 (1984)
[4] Buckingham, M. A.; Golumbic, M. C., Partitionable graphs, circle graphs, and the Berge strong perfect graph conjecture, Discrete Math., 44, 45-54 (1983) · Zbl 0507.05052
[5] Gavril, F., A recognition algorithm for the intersection graphs of paths in trees, Discrete Math., 23, 211-227 (1978) · Zbl 0398.05060
[6] Giles, R.; Trotter, L. E.; Tucker, A., The strong perfect graph theorem for a class of partitionable graphs, (Berge, C.; Chvátal, V., Perfect Graphs. Perfect Graphs, Ann. Discrete Math., 21 (1984)) · Zbl 0555.05043
[7] Golumbic, M. C., (Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York) · Zbl 0541.05054
[8] M. C. Golumbic and R. E. JamisonDiscrete Math.; M. C. Golumbic and R. E. JamisonDiscrete Math. · Zbl 0568.05023
[9] Grinstead, C. M., The strong perfect graph conjecture for toroidal graphs, J. Combin. Theory Ser. B, 30, 70-74 (1981) · Zbl 0475.05031
[10] Jamison-Waldner, R. E., Partition numbers for trees and ordered sets, Pacific J. Math., 96, 115-140 (1981) · Zbl 0482.52010
[11] Jamison-Waldner, R. E., A perspective on abstract convexity: Classifying alignments by varieties, (Kay, D. C.; Breen, M., Convexity and Related Combinatorial Geometry (1982), Dekker: Dekker New York/Basel), 113-150 · Zbl 0482.52001
[12] Kelmans, A. K., Graph Theory Newsletter, 9, No. 1 (September 1979)
[13] Kelmans, A. K., The strong perfect graph conjecture for certain class of graphs, (Proc. 27th Int. Wiss. Koll. Tech. Hochsch. Ilmenau (October 1982)) · Zbl 0494.05036
[14] Lipski, W., Information storage and retrieval—Mathematical foundations, II, Theoret. Comput. Sci., 3, 183-211 (1976) · Zbl 0352.68121
[15] Lobb, W. A., Perfect graphs from paths in trees, (presented at the “11th Sympos. on Mathematical Programming”. presented at the “11th Sympos. on Mathematical Programming”, Bonn (August 1982))
[16] Nishizeki, T.; Terada, O.; Leven, D., (Algorithms for Edge-Coloring Graphs (April 1983), Dept. of Electrical Comm., Tohoku University: Dept. of Electrical Comm., Tohoku University Sendai), TRESIS 83001
[17] Parthasarathy, K. R.; Ravindra, G., The strong perfect graph conjecture is true for \(K_{1,3}\)-free graphs, J. Combin. Theory Ser. B, 21, 212-223 (1976) · Zbl 0297.05109
[18] Parthasarathy, K. R.; Ravindra, G., The validity of the strong perfect graph conjecture for \((K_{4-e})\)-free graphs, J. Combin. Theory Ser. B., 26, 98-100 (1979) · Zbl 0416.05062
[19] Renz, P. L., Intersection representations of graphs by arcs, Pacific J. Math., 34, 501-510 (1970) · Zbl 0191.55103
[20] Shannon, C. E., A theorem on coloring the lines of a network, J. Math. Phys., 28, 148-151 (1949) · Zbl 0032.43203
[21] M. M. Sysloin; M. M. Sysloin
[22] Syslo, M. M., (On Characterizations of Cycle Graphs and on Other Families of Intersection Graphs (June 1978), Institute of Computer Science, University of Wroclaw: Institute of Computer Science, University of Wroclaw Poland), Report No. N-40 · Zbl 0412.05057
[23] Syslo, M. M., The Helly-type property of nontrivial intervals on a tree, Discrete Math., 37, 297-298 (1981) · Zbl 0476.05032
[24] R. E. TarjanDiscrete Math.; R. E. TarjanDiscrete Math. · Zbl 0572.05039
[25] Trotter, L. E., Line perfect graphs, Math. Programming, 12, 255-259 (1977) · Zbl 0366.05043
[26] Tucker, A., The strong perfect graph conjecture for planar graphs, Canad. J. Math., 25, 103-114 (1973) · Zbl 0251.05102
[27] Tucker, A., Coloring a family of circular arcs, SIAM J. Appl. Math., 29, 493-502 (1975) · Zbl 0312.05105
[28] Tucker, A., Critical perfect graphs and perfect 3-chromatic graphs, J. Combin. Theory Ser. B, 23, 143-149 (1977) · Zbl 0376.05047
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.