engleski

On Path Graphs of Bipartite Graphs

We consider all graphs to be simple and finite. The set of vertices of graph G is denoted by V(G) and the set of edges by E(G). A clique is a set of vertices every pair of which are adjacent. The cardinality of a largest clique in graph G is denoted by $\omega (G)$. A vertex colouring of a graph G=(V(G), E(G)) is a mapping $c:V(G) \rightarrow K$, such that $c(v) \neq c(w)$ whenever v and w are adjacent. The elements of the set K are called the available colours. The set of vertices which are mapped to one colour is called colour class. A chromatic number of G, denoted by $\chi(G)$, is the smallest integer k, such that G has a colouring $c:V(G) \rightarrow \{ 1, \ldots, k \}$. Obviously, $\omega(G) \le \chi(G)$, since each two vertices of a clique are adjacent and therefore must be in distinct colour classes. For $S \subseteq V(G)$ an induced subgraph G(S) of a graph G is a graph with vertex set S and edge set consisting of all the edges of G with both ends in S. A graph G is perfect if $\omega(H) = \chi(H)$ for every induced subgraph H of G. The following theorem, known as the Perfect Graph Theorem, is proved by Lov\'asz in 1972 (see [3]): Theorem 1 Graph G is perfect if and only if its complement $\overline G$ is perfect. The line graph L(G) of a graph G is the graph with the set of vertices V(L(G))=E(G) in which two vertices are adjacent if and only if the corresponding edges of G are adjacent. Bipartite graphs and line graphs of bipartite graphs are perfect (see [2]). Perfect Graph Theorem implies that the complements of bipartite graphs and the complements of line graphs of bipartite graphs are perfect. For a given graph G and a positive integer k the $P_k$-path graph $P_k(G)$ has for vertices the set of paths of length k in G. Two vertices are connected in $P_k(G)$ when the intersection of the corresponding paths forms a path of length k-1 in G, and their union forms either a cycle or a path of length k+1. Path graphs are introduced as a generalization of line graphs (see [1]). Obviously, $P_1(G)$ coincides with the L(G). We prove the following theorem: Theorem 2 Path graphs of bipartite graphs are perfect. Corollary 1 Complements of path graphs of bipartite graphs are perfect. REFERENCES [1] H.J. Broersma, C. Hoede, Path Graphs, J. Graph Theory 13, No. 4 (1989), 427--444. [2] G. Cornu\'ejols, "The Strong Perfect Graph Conjecture", Proceedings of the International Congress of Mathematicians, 2002, Beijing, Vol. III: Invited Lectures, Li Tatsies, (Editor), Higher Education Press, Beijing (2002), pp. 547--559. [3] L. Lov\'asz, Normal Hypergraphs and the Perfect $G$raph Conjecture, Discrete Math. 2 (1972), 253--267.

path graph; biparite graph; perfect graph

nije evidentirano