Circular-Perfect Concave-Round Graphs

摘要

For 1 ≤ d ≤ k — d, K_(k/d) denotes the graph with vertices 0,1,... ,k — 1, in which i is adjacent to j if and only if d ≤ |i - j| ≤ k — d. A graph G is circular-perfect if, for every induced subgraph H of G, the infinum k/d for which H admits a homomorphism to K_(k/d) is equal to the supremum k/d for which K_(k/d) admits a homomorphism to H. We answer a question af Bang-Jensen and Huang by giving a complete characterization of circular-perfect concave-round graphs.