On Almost Bipartite Large Chromatic Graphs

Abstract

This chapter discusses problems related to bipartite large chromatic graphs. It is assumed that the chromatic number χ(Ң) of a graph Ң is greater than κ, a finite or infinite cardinal. This problem is investigated in the chapter, in case some other restrictions are imposed on Ң as well. The results show that χ(Ң) can be arbitrarily large while the finite subgraphs are very close to bipartite graphs. This topic is a strange mixture of finite combinatorics and set theory. There is a striking difference between large chromatic finite and infinite graphs, which was discovered by the first two authors about fifteen years ago. While for any k < ω there are finite graphs with χ(Ң) >κ without any short circuits, a graph with χ(Ң) > κ ≥ ω has to contain a complete bipartite graph [k, κ+] for all k< ω. Hence, such a graph contains all finite bipartite graphs, though it may avoid short odd circuits. The chapter discusses some standard examples and the ordered edge graph, omitting the vertices of subgraphs, omitting edges of a subgraph, through several lemmas, definitions, corollaries, and theorems.

Locations

• CiteSeer X (The Pennsylvania State University) - View - PDF
• North-Holland mathematics studies - View