Abstract Consider a graph G and a positive integer k. The maximum k‐coloring problem is to color a maximum number of vertices using k colors, such that no two adjacent vertices have the same color. The maximum k‐covering problem is to find k disjoint cliques covering a maximum number of vertices. The present paper contains polynomial time algorithms for finding maximum k‐colorings and maximum k‐coverings of transitive graphs.

Abstract Consider a hypergraph H = (E, P) where E denotes the set of vertices and P the set of edges. The hypergraph H = (E, P) is called an edge‐tree hypergraph if there exists a tree T with edge set E such that every p = P is a path in T. We describe a polynomial time algorithm for deciding whether a given hypergraph H = (E, P) is an edge‐tree hypergraph. The algorithm can be used to decide whether a binary matroid is graphic or not.

Abstract A graph H is called total if there exists a graph G such that there is a one‐to‐one correspondence between the vertices of H and the vertices and edges of G such that two vertices of H are adjacent iff the corresponding elements of G are adjacent or incident. In this paper we present a linear time algorithm for the recognition of the total graphs. The algorithm is based on the breadth‐first search technique.

Abstract Consider a finite family of non‐empty sets. The intersection graph of this family is obtained by representing each set by a vertex, two vertices being connected by an edge if and only if the corresponding sets intersect. The intersection graph of a family of arcs on a circularly ordered set is called a circular‐arc graph. In this paper we give a characterization of the circular‐arc graph and we describe efficient algorithms for recognizing two subclasses. Also, we describe efficient algorithms for finding a maximum independent set, a minimum covering by cliques and a maximum clique of a circular‐arc graph.

Abstract Consider a family of chords in a circle. A circle graph is obtained by representing each chord by a vertex, two vertices being connected by an edge when the corresponding chords intersect. In this paper, we describe efficient algorithms for finding a maximum clique and a maximum independent set of circle graphs. These algorithms require at most n3 steps, where n is the number of vertices in the graph.

A finite undirected graph is called chordal if every simple circuit has a chord. Given a chordal graph, we present, ways for constructing efficient algorithms for finding a minimum coloring, a minimum covering by cliques, a maximum clique, and a maximum independent set. The proofs are based on a theorem of D. Rose [3] that a finite graph is chordal if and only if it has some special orientation called an R-orientation. In the last part of this paper we prove that an infinite graph is chordal if and only if it has an R-orientation.