A note on superbrittle graphs

AbstractPerfectly orderable graphs are such that an ordering x1>2>…>xn of the nodes can be found for which the sequential node coloring algorithm based on this order (“always use the smallest possible color”) gives an optimum coloring for any subgraph.We characterize in terms of forbidden subgraphs two subclasses of perfectly orderable graphs: the superbrittle graphs are such that in any subgraph a node x can never be a midpoint of an induced P4 (path on 4 nodes) and an endpoint of an induced P4. Maxibrittle graphs are such that in any subgraph there is no induced P4 having a node of maximum degree as an endpoint and there is no induced P4 having a node of minimum degreeas a midpoint