Hell, Pavol; Huang, Jing Two remarks on circular arc graphs. (English) Zbl 0868.05043 Graphs Comb. 13, No. 1, 65-72 (1997). A graph \(G\) is said to be a circular arc graph if there exist circular arcs A\(g\), \(g\in V(G)\), such that \(g\), \(g'\) are adjacent in \(G\) if and only if the corresponding A\(g\), A\(_{g'}\) intersect. This paper shows that a graph with clique covering number two is a circular arc graph if and only if its edges can be coloured by two colours so that no induced four-cycle contains two opposite edges of the same colour. Reviewer: Ma Zhongfan (Beijing) Cited in 14 Documents MSC: 05C75 Structural characterization of families of graphs 68R10 Graph theory (including graph drawing) in computer science Keywords:clique covering number; circular arc graph PDFBibTeX XMLCite \textit{P. Hell} and \textit{J. Huang}, Graphs Comb. 13, No. 1, 65--72 (1997; Zbl 0868.05043) Full Text: DOI References: [1] Apostolico, A., Hambrusch, S.E.: Finding maximum cliques on circular arc graphs. Information Processing Letters26, 209-215 (1987) · Zbl 0654.68082 [2] Bhattacharya, B., Kaller, D.M.: AnO(m+nlogn) algorithm for the maximum clique problem in circular arc graphs. Simon Fraser University CSS/LCCR TR 94-26 [3] Bhattacharya, B., Hell, P., Huang, J.: A linear algorithm for maximum cliques in proper circular arc graphs. SIAM J. on Discrete Math (in press) · Zbl 0854.05092 [4] Eschen, E.M., Spinrad, J.:O(n 2) recognition and isomorphism algorithms for circular-arc graphs. Proc 4th Ann SODA, pp. 128-137 · Zbl 0801.68128 [5] Feder, T., Hell, P., Huang, J.: List homomorphisms and circular arc graphs, submitted to Combinatorica · Zbl 0985.05048 [6] Gallai, T.: Transitiv orientbare Graphen, Acta Math. Acad. Sci. Hungar.18, 25-66 (1967) · Zbl 0153.26002 [7] Gavril, F.: Algorithms on circular-arc graphs. Networks4, 357-369 (1974) · Zbl 0309.05126 [8] Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, Academic Press, N.Y. (1980) · Zbl 0541.05054 [9] Hell, P., Huang, J.: Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs. J. Graph Theory20, 361-374 (1995) · Zbl 0835.05064 [10] Hsu, W.L.: Maximum weight clique algorithms for ciruclar arc graphs and circle graphs. SIAM J. Comput.14, 224-231 (1985) · Zbl 0567.68042 [11] Hsu, W.L.:O(mn) algorithms for the recognition and isomorphism problems on circular-arc graphs. SIAM J. Comput.24, 411-439 (1995) · Zbl 0831.68051 [12] Shih, W.K., Hsu, W.L.: AnO(nlogn+mloglogn) maximum weight clique algorithm for circular arc graphs. Information Processing Letters31, 129-134 (1989) · Zbl 0677.68056 [13] Spinrad, J.: Circular-arc graphs with clique cover number two. J. Combinatorial TheoryB 300-306 (1988) · Zbl 0596.05042 [14] Stouffers, K.E.: Scheduling of traffic lights ? a new approach. Transportation Res.2, 199-234 (1968) [15] Trotter, W.T., Moore, J.I.: Characterization problems for graphs, partially ordered sets, lattices, and families of sets. Discrete Math.16, 361-381 (1976) · Zbl 0356.06007 [16] Tucker, A.: Matrix characterization of circular arc graphs. Pacific J. Math.39-2, 535-545 (1971) · Zbl 0226.05125 [17] Tucker, A.: Colouring a family of circular arcs. SIAM J. Appl. Math.29, 493-502 (1975) · Zbl 0312.05105 [18] Tucker, A.: An efficient test for circular arc graphs. SIAM J. Comput.9, 1-24 (1980) · Zbl 0453.05054 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.