{'fraction_non_alphanumeric': 0.025167785234899327, 'fraction_numerical': 0.0025167785234899327, 'mean_word_length': 4.965, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Linear-Time Algorithm for Recognition of Catval Graphs

We give a linear-time algorithm for recognizing graphs that can be represented as the intersection graph of connected subgraphs of a caterpillar. 1 Motivation and background The interval graphs and chordal graphs are well-known classes of intersection graphs, arising respectively from connected subpaths of a path, and from connected subtrees of a tree. In a recent paper [7] a class of graphs lying properly between interval and chordal graphs was introduced, the so-called catval graphs. The motivation for studying catval graphs came from memory requirement considerations in dynamic programming algorithms on graphs of bounded treewidth. However, the problem of recognizing catval graphs was not addressed since the characterization given in [7] hints only at a brute force algorithm of complexity O(n). In this short note we give a lineartime algorithm for this problem. In essence the algorithm follows from the well-known linear-time algorithms for recognition of interval graphs and the following characterization which we give in the next section: ’G is a catval graph iff the graph G \ {v : v simplicial in G} is interval’.