GRAPHICAL CONFLICT I: A NEW CLASS OF EXTREMAL PROBLEMS

Abstract

Inspired by the analogy with the three traditional types of conflict in psychology (approach/approach, approach/avoid, and avoid/avoid), we consider corresponding types of extremal problems in graph theory. These are translated into the determination of extremal values of the product or quotient of two graphical parameters, subject to given constraints. For purposes of exemplification, we study and determine both the exact solution and the extremal graphs for several products and quotients which include confrontations of (a) point- and line-independence and covering, (b) connectivity and coloring, (c) covering and connectivity. We conclude with an indication of several unsolved problems for future research.