Recognition of chordal graphs and cographs which are Cover-Incomparability graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910704725917696 |
|---|---|
| author | Anil, Arun Changat, Manoj |
| author_facet | Anil, Arun Changat, Manoj |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_13964 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Recognition of chordal graphs and cographs which are Cover-Incomparability graphs Anil, Arun Changat, Manoj Combinatorics Discrete Mathematics 05C75, 05C85 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. |
| title | Recognition of chordal graphs and cographs which are Cover-Incomparability graphs |
| topic | Combinatorics Discrete Mathematics 05C75, 05C85 |
| url | https://arxiv.org/abs/2307.13964 |