Graphs having circuits with at least two chords |
| |
Authors: | Heinz-Jürgen Voss |
| |
Affiliation: | Technische Hochschule Ilmenau, Ilmenau, German Democratic Republic |
| |
Abstract: | All 2-connected non-bipartite graphs are characterized which have a minimal valency ≥3 and which have no odd circuit with two or more chords. From this it is derived that in each graph with chromatic number ≥4 containing no complete 4-graph there is an odd circuit with two or more chords. This result was conjectured by P. Erdös. Corresponding results for even circuits and for circuits with a fixed edge are obtained. Some related problems of the Turán type are solved. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |