vix.ing · top · new · best · stats · spec

2-subcoloring is NP-complete for planar comparability graphs

2017/08/31 by Pascal Ochem · 1 citation
Computer Science · Engineering · Mathematics · #1-planar graph #Advanced Graph Theory Research #Chordal graph #Clique-sum #Cograph #Combinatorics #Comparability #Complexity and Algorithms in Graphs #Discrete mathematics #Graph #Indifference graph #Line graph #Mathematics #Maximal independent set #Outerplanar graph #Partition (number theory) #Pathwidth #Planar graph #Vertex (graph theory) #graph theory and CDMA systems

paper · doi:10.1016/j.ipl.2017.08.004

openalex publication_date 2017/08/31 · crossref created 2017/08/31 · crossref issued 2017/12/01 · crossref published 2017/12/01 · crossref published-print 2017/12/01 · crossref deposited 2019/12/05 · crossref indexed 2024/07/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/23

Citations

Cited by