2018/08/29 by Martin Dyer, Haiko Müller, Dyer, Martin +1
Computer Science · Mathematics · #05C30 05C85 #Advanced Graph Theory Research #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #G.2.1 #G.2.2 #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · doi:10.48550/arxiv.1808.09853
openalex publication_date 2018/08/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that the number of independent sets in cocomparability graphs can be counted in linear time, as can counting cliques in comparability graphs. By contrast, counting cliques in cocomparabilty graphs and counting independent sets in comparability graphs are #P-complete. We extend these results to counting maximal cliques and independent sets. We also consider the fixed-parameter versions of counting cliques and independent sets of given size k. Finally, we combine the results to show that both counting cliques and independent sets in permutation graphs are in linear time.