First-order logic with metric betweenness – the case of non-definability of some graph classes

Abstract

The metric betweenness of a connected graph and arbitrary graphs is FO definable. Moreover, several interesting classes of graphs with strong distance properties are shown to be FO definable using metric betweenness. However, there are different classes that do not possess such an FO axiomatization. The main goal of this note is to show that certain classes of graphs do not allow an axiomatization in First-Order Logic with Betweenness (FOLB).

Keywords

• First-order logic
• n-colorable
• n-connected
• perfect graph
• probe chordal
• matching