Tuyển tập các báo cáo nghiên cứu khoa học hay nhất của tạp chí toán học quốc tế đề tài: Another infinite sequence of dense triangle-free graphs. | Another infinite sequence of dense triangle-free graphs Stephan Brandt FB Mathematik Informatik WE 2 Freie Universitat Berlin Arnimallee 3 14195 Berlin Germany brandt@ Tomaz Pisanski University of Ljubljana Faculty of Mathematics and Physics and IMFM TCS Jadranska 19 Ljubljana Slovenia Submitted February 26 1998 Accepted July 27 1998 AMS Subject classifications 05C75 05C35 Abstract The core is the unique homorphically minimal subgraph of a graph. A triangle-free graph with minimum degree Ỏ n 3 is called dense. It was observed by many authors that dense triangle-free graphs share strong structural properties and that the natural way to describe the structure of these graphs is in terms of graph homomorphisms. One infinite sequence of cores of dense maximal triangle-free graphs was known. All graphs in this sequence are 3-colourable. Only two additional cores with chromatic number 4 were known. We show that the additional graphs are the initial terms of a second infinite sequence of cores. Let G and H be graphs. A homomorphism G H is a function ơ V G V H mapping edges on edges . vw 2 E G implies a v a w 2 E H . Every graph G has a unique minimal subgraph G0 with G G0 which is called the core for an introduction and relevant literature see 6 . Note that the core of G has the same chromatic number as G. A triangle-free graph is maximal if for every pair of non adjacent vertices u v the addition of the edge uv creates a triangle. Note that a triangle-free graph of order n 3 is maximal if and only if it has diameter 2. Let u1 u2 be two non-adjacent vertices of a maximal triangle-free graph G. Assume that there is a vertex v1 which 1 THE ELECTRONIC .JOURNAL OF COmBINATORICS 5 1998 R43 2 is adjacent to u1 but not to u2. Since u2 and v1 are not adjacent they must have a common neighbour v2. Therefore a u1 ơ u2 for any homomorphism Ơ from G to a triangle-free graph. It follows that a w1 ơ w2 implies that the set of neighbours
