On chordal proper circular arc graphs

Discrete Mathematics North-Holland

395

128 (1994) 395-398

Note

On chordal proper circular arc graphs* Jmgen Department

Bang-Jensen of Mathematics

and Computer Science, Odense University,

DK-5230 Denmark

Pavol Hell School of Computing Science, Simon Fraser University.

B.C., Canada USA 156

Received 19 August 1991 Revised 3 April 1992

Abstract Wegner proved that a chordal graph is a proper interval graph if and only if it is claw-free, net-free and tent-free. We observe that in fact the characterization can be refined to say that a chordal graph is a proper interval graph if and only if it is claw-free, net-free and not a multiple of the tent. This observation implies that a chordal graph is a proper circular arc graph if and only if it is claw-free and net-free. A further implication of this result is that a chordal graph can be oriented as a local tournament - an oriented graph in which the predecessors as well as the successors of any vertex induce a tournament - if and only if it is claw-free and net-free.

A chordal graph is a graph in which every cycle of length at least four has a chord. A graph is an interval graph if it is the intersection graph of a family of intervals on the real line. A graph is a circular arc graph if it is the intersection graph of a family of arcs on a circle. An interval graph (resp. circular arc graph) is proper if the family of intervals (resp. of arcs) can be chosen to be inclusion-free. Wegner ([6], cf. also [4,2, p. 1951) characterized the chordal graphs which are proper interval graphs as precisely those that are claw-free, net-free and tent-free (see

Correspondence to: J. Bang-Jensen, Department of Mathematics and Computer Science, Odense University, DK-5230, Denmark. *This note was written while the authors where visiting the Laboratoire de Recherche en Informatique, Universite de Paris&d, whose hospitality and financial support is gratefully acknowledged. 0012-365X/94/$07.00 0 1994-Elsevier SSDI 0012-365X(92)00458-0

Science B.V. All rights reserved

J. Bang-Jensen, P. Hell

396

1

A

Claw

Net

A Tent

Fig. 1. The Claw, the Net, and the Tent

Fig. 1). We extend this to a characterization of the chordal graphs which are proper circular arc graphs. It turns out that only the claw and the net are forbidden as induced subgraphs. The essence of the extension is a more detailed characterization of chordal proper interval graphs. We say that a graph G is a multiple of another graph H if G can be obtained from H by replacing each vertex x of H by a complete graph K, and joining vertices of different complete graphs K,, K, if and only if x and y are adjacent in H. Theorem 1. Let G be a graph which contains no induced claw, net, four-cycle, or jive-cycle. If G contains the tent as an induced subgraph, then G is a multiple of the tent. Proof. We prove the statement by induction on the number of vertices of G. Since the statement is obvious for graphs with 6 vertices, we may assume that G has at least 7 vertices. There exists a vertex v such that G-v is connected and contains the tent as an induced subgraph (this can be seen for example by contracting the tent and taking for Dan end vertex, other than the contracted tent, in a spanning tree of the resulting graph). By induction, G-v is a multiple of the tent. Let the complete subgraphs of G - v that correspond to the vertices of the tent be labelled as in Fig. 2. Since G is connected, v has a neighbour. Note that v cannot have neighbours in all three sets Ai, because there would be an induced claw. On the other hand, v must have a neighbour in some Bj, since otherwise G contains an induced net or an induced four-cycle. We may assume, without loss of generality, that v has a neighbour in B2. Then v is joined to all of A1 or all of A3 or else there would be an induced claw. We assume, without loss of generality, that u is adjacent to all vertices of Al. Suppose v is not adjacent to any vertex of A2 u AS. Then v must be adjacent to all the vertices of the sets B2 and BS. For otherwise G would contain an induced claw if v had a neighbour in, say, B2 and a nonneighbour in B3, or an induced net otherwise. Furthermore, v has no neighbours in B1 or else G has an induced claw centred in B1. Thus in this case v can be inserted in the set AI, and G is a multiple of the tent.

Chordal proper circular arc graphs

397

Fig. 2. The labelling of the vertices of G in the proof of Theorem I

Thus in addition to Al, u is adjacent to some vertices of, say, AZ. Then u is completely adjacent to all vertices of B1, B2, B3, or else G would contain an induced four- or five-cycle (this last case occurs when o is not adjacent to any vertex of B1 u Bz .) Now u is in fact adjacent to all vertices of AZ, or else G has an induced claw centred in B, . Since u is not adjacent to any vertex of AJ, it can be inserted in the set &, and so G is a multiple of the tent. 0 Corollary 2. A chordal graph G is a proper interual graph ifand only ifit is claw-free and net-free and is not a multiple of the tent. Corollary 3. A chordal graph G is a proper circular arc graph ifand only ifit is claw-free and net-free. Proof. It is easy to see that neither a claw nor a net is a proper circular arc graph. So

by Theorem 1, it is enough to show that any multiple of a tent is a proper circular arc graph. It is easy to find a proper circular arc representation of the tent. Such a representation may be extended to a representation of any multiple of the tent in an obvious manner. 0 One can interpret our observations as showing that, in the class of chordal graphs, the multiples of a tent are the only graphs that distinguish proper interval graphs from proper circular arc graphs. A local tournament is an oriented graph for which the in-neighbours as well as the out-neighbours of any vertex induce a tournament. Local tournaments were introduced in [l]. It was shown in [l] that many of the nice structural properties of tournaments still hold for local tournaments, for example every connected local

398

J. Bang-Jensen, P. Hell

tournament has a hamilton path and every strongly connected local tournament has a hamilton cycle. In [3] linear algorithms are given for finding a hamilton path and a longest cycle in arbitrary local tournaments. Corollary 4. A chordal graph is orientable as a local tournament if and only if it is claw-free and net-free.

Proof. It was shown in [S] (cf. also [3]) that a graph is orientable tournament if and only if it is a proper circular arc graph. 0

as a local

References [l] J. Bang-Jensen, Locally semicomplete digraphs: a generalization of tournaments, J. Graph Theory 14 (1990) 371-390. [Z] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs (Academic Press, New York, 1980). [3] P. Hell, J. Bang-Jensen and J. Huang, Local tournaments and proper circular arc graphs, Lecture Notes in Computer Science, Vol. 450 (Springer, Berlin, 1990) 101-108. [4] F.S. Roberts, Indifference graphs, in: F. Harary ed., Proof techniques in Graph Theory (Academic Press, New York, 1969) 139-146. [S] D. J. Skrien, A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular arc graphs, and nested interval graphs, J. Graph Theory 6 (1982) 309-316. [6] G. Wegner, Eigenschaften der nerven homologische-einfactor familien in R”, Ph.D. Thesis, Gottingen, 1967.