A New Four-Color Problem

Abstract

Suppose that T is a normal spanning tree (depth-first search tree) of a graph G. If e=xy and e′=uv are edges of G, satisfying x≺Tu≺Ty≺Tv, then they are called secant edges of G with respect to T. Suppose that G has no secant edges with respect to T. If T is a path, Ghazal and Al-Mniny proved that the chromatic number is at most 3. We conjecture that there is a positive constant γ such that, for any graph G that has no secant edges with respect to a normal spanning tree T, then χ(G)≤γ. We pose the problem of whether γ=4 suffices. We establish a positive answer in the case where T has at most one node.