2021/11/30 by Santiago Guzmán‐Pro, Pavol Hell, Guzmán-Pro, Santiago +3 · 1 citation
Biochemistry, Genetics and Molecular Biology · #Combinatorics (math.CO) #FOS: Mathematics #melanin and skin pigmentation
paper · pdf · doi:10.48550/arxiv.2112.00154
openalex publication_date 2021/11/30 · openalex created_date 2022/05/05 · openalex updated_date 2026/07/28
Each hereditary property can be characterized by its set of minimal obstructions; these sets are often unknown, or known but infinite. By allowing extra structure it is sometimes possible to describe such properties by a finite set of forbidden objects. This has been studied most intensely when the extra structure is a linear ordering of the vertex set. For instance, it is known that a graph G is k-colourable if and only if V(G) admits a linear ordering ≤ with no vertices v1 ≤ ⋯ ≤ vk+1 such that vi vi+1 ∈ E(G) for every i ∈ \ 1, …, k \. In this paper, we study such characterizations when the extra structure is a circular ordering of the vertex set. We show that the classes that can be described by finitely many forbidden circularly ordered graphs include forests, circular-arc graphs, and graphs with circular chromatic number less than k. In fact, every description by finitely many forbidden circularly ordered graphs can be translated to a description by finitely many forbidden linearly ordered graphs. Nevertheless, our observations underscore the fact that in many cases the circular order descriptions are nicer and more natural.