×

On the \(L(h, k)\)-labeling of co-comparability graphs and circular-arc graphs. (English) Zbl 1167.05043

Summary: Given two nonnegative integers \(h\) and \(k\), an \(L(h, k)\)-labeling of a graph \(G = (V, E)\) is a map from \(V\) to a set of integer labels such that adjacent vertices receive labels at least \(h\) apart, while vertices at distance at most 2 receive labels at least \(k\) apart. The goal of the \(L(h, k)\)-labeling problem is to produce a legal labeling that minimizes the largest label used. Since the decision version of the \(L(h, k)\)-labeling problem is NP-complete, it is important to investigate classes of graphs for which the problem can be solved efficiently. Along this line of thought, in this article we deal with co-comparability graphs, its subclass of interval graphs, and circular-arc graphs. To the best of our knowledge, ours is the first reported result concerning the \(L(h, k)\)-labeling of co-comparability and circular-arc graphs. In particular, we provide the first algorithm to \(L(h, k)\)-label co-comparability, interval, and circular-arc graphs with a bounded number of colors. Finally, in the special case where \(k = 1\) and \(G\) is an interval graph, our algorithm improves on the best previously-known ones using a number of colors that is at most twice the optimum.

MSC:

05C78 Graph labelling (graceful graphs, bandwidth, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aly, A class of scalable optical interconnection networks through discrete broadcast-select multi-domain WDM, Proc IEEE INFOCOM, Toronto, Canada pp 392– (1994)
[2] Baker, Partial orders of dimension two, Networks 2 pp 11– (1971)
[3] Bertossi, Channel assignment on strongly-simplicial graphs, Proc Int Parallel and Distributed Processing Symp (IPDPS ’03), Nice, France (2003)
[4] Blelloch, Accounting for memory bank contentions and delay in high-bandwidth multiprocessors, IEEE Trans Parallel Distributed Syst 8 pp 943– (1997)
[5] Bondy, Graph theory with applications (1976) · Zbl 1226.05083 · doi:10.1007/978-1-349-03521-2
[6] Booth, Testing for the consecutive ones property, interval graphs and graph planarity using PQ-tree algorithms, J Comput Syst Sci 13 pp 335– (1976) · Zbl 0367.68034 · doi:10.1016/S0022-0000(76)80045-1
[7] Booth, A linear time algorithm for deciding interval graph isomorphism, J ACM 26 pp 183– (1979) · Zbl 0402.68050
[8] Calamoneri, Exact solution of a class of frequency assignment problems in cellular networks and other regular grids, Discrete Math Theor Comput Sci 8 pp 141– (2006)
[9] Calamoneri, The L(h, k)-labelling problem: an annotated bibliography and a survey, The Computer Journal 49 pp 585– (2006)
[10] Corneil, Extensions of permutation and interval graphs, Proc 18th Southeastern Conference on Combinatorics, Graph Theory and Computing pp 267– (1987) · Zbl 0652.05055
[11] Corneil, On subfamilies of AT-free graphs, SIAM J Discrete Math 20 pp 241– (2006) · Zbl 1110.05092
[12] Corneil, Asteroidal triple-free graphs, SIAM J Discrete Math 10 pp 399– (1997) · Zbl 0884.05075
[13] Damaschke, Distance in cocomparability graphs and their powers, Disc Appl Math 35 pp 67– (1992) · Zbl 0747.05075
[14] Das, Conflict-free star-access in parallel memory systems, J Parallel Distributed Comput 66 pp 1431– (2006) · Zbl 1178.68074
[15] Degan, Trapezoid graphs and their coloring, Discrete Appl Math 21 pp 35– (1988)
[16] Even, Permutation graphs and transitive graphs, J ACM 19 pp 400– (1972) · Zbl 0251.05113
[17] Gallai, Transitiv orientierbare Graphen, Acta Math Acad Sci Hungar 18 pp 25– (1967)
[18] Garey, Computers and intractability - a guide to the theory of NP-completeness (1979) · Zbl 0411.68039
[19] Garey, The complexity of coloring circular arcs and chords, SIAM J Algebraic Discrete Methods 1 pp 185– (1980) · Zbl 0499.05058
[20] Golumbic, Algorithmic graph theory and perfect graphs (1980) · Zbl 0541.05054
[21] Golumbic, Graph sandwich problems, J Algorithms 19 pp 449– (1995) · Zbl 0838.68054
[22] Goldberg, Four strikes against physical mapping of DNA, J Computat Biol 2 pp 139– (1995)
[23] Golumbic, Tolerance graphs, Discrete Appl Math 9 pp 157– (1984) · Zbl 0547.05054
[24] Griggs, Labeling graphs with a condition at distance 2, SIAM J Discrete Math 5 pp 586– (1992)
[25] van den Heuvel, Graph labelling and radio channel assignment, J Graph Theory 29 pp 263– (1998) · Zbl 0930.05087
[26] Jamison, Elimination orderings of chordal graphs, Proc of the Seminar on Combinatorics and Applications pp 192– (1982) · Zbl 0703.05049
[27] Jensen, Graph coloring problems (1995) · Zbl 0855.05054
[28] Kratsch, Domination on cocomparability graphs, SIAM J Discrete Math 6 pp 400– (1993) · Zbl 0780.05032
[29] Lekkerkerker, Representation of a finite graph by a set of intervals on the real line, Fundam Math 51 pp 45– (1962) · Zbl 0105.17501
[30] Looges, Optimal greedy algorithms for indifference graphs, Comput Math Appl 25 pp 15– (1993) · Zbl 0794.68115
[31] McCormick, Optimal approximation of sparse Hessians and its equivalence to a graph coloring problem, Math Program 26 pp 153– (1983) · Zbl 0507.65027
[32] R. M.Karp, Mapping the genome: some combinatorial problems arising in molecular biology, Proc. 25th Ann. ACM Symp. on Theory of Comp. (STOC ’93), San Diego, CA, 1993, pp. 278-285. · Zbl 1310.92022
[33] Olariu, An optimal greedy heuristic to color interval graphs, Inform Process Lett 37 pp 21– (1991) · Zbl 0711.68083
[34] Pe’er 979 pp 142– (1995)
[35] Pe’er, Realizing interval graphs with side and distance constraints, SIAM J Discrete Math 10 pp 662– (1997)
[36] Raychauduri, On powers of interval and unit interval graphs, Congressus Numerantium 59 pp 235– (1987)
[37] Raychauduri, On powers of strongly chordal and circular arc graphs, Ars Combinatoria 34 pp 147– (1992)
[38] Rose, Algorithmic aspects of vertex elimination on graphs, SIAM J Comput 5 pp 266– (1976) · Zbl 0353.65019
[39] Sakai, Labeling chordal graphs: distance two condition, SIAM J Discrete Mathe 7 pp 133– (1994) · Zbl 0794.05118
[40] Shapiro, Theoretical limitations on the efficient use of parallel memories, IEEE Trans Comput 17 pp 421– (1978) · Zbl 0379.68043
[41] Tarjan, Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs and selectively reduce acyclic hypergraphs, SIAM J Comput 13 pp 566– (1984) · Zbl 0545.68062
[42] Wan, Near-optimal conflict-free channel set assignments for an optical cluster-based hypercube network, J Combin Optim 1 pp 179– (1997) · Zbl 0883.68014
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.