Arun Anil ; Manoj Changat - Recognition of chordal graphs and cographs which are Cover-Incomparability graphs

dmtcs:11657 - Discrete Mathematics & Theoretical Computer Science, November 15, 2024, vol. 26:3 - https://doi.org/10.46298/dmtcs.11657
Recognition of chordal graphs and cographs which are Cover-Incomparability graphsArticle

Authors: Arun Anil ; Manoj Changat

    Cover-Incomparability graphs (C-I graphs) are an interesting class of graphs from posets. A C-I graph is a graph from a poset $P=(V,\le)$ with vertex set $V$, and the edge-set is the union of edge sets of the cover graph and the incomparability graph of the poset. The recognition of the C-I graphs is known to be NP-complete (Maxová et al., Order 26(3), 229--236(2009)). In this paper, we prove that chordal graphs having at most two independent simplicial vertices are exactly the chordal graphs which are also C-I graphs. A similar result is obtained for cographs as well. Using the structural results of these graphs, we derive linear time recognition algorithms for chordal graphs and cographs which are C-I graphs.


    Volume: vol. 26:3
    Section: Discrete Algorithms
    Published on: November 15, 2024
    Accepted on: October 2, 2024
    Submitted on: July 27, 2023
    Keywords: Mathematics - Combinatorics,Computer Science - Discrete Mathematics,05C75, 05C85

    Classifications

    Consultation statistics

    This page has been seen 67 times.
    This article's PDF has been downloaded 28 times.