# Questions tagged [chordal-graphs]

A chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle.

8 questions
Filter by
Sorted by
Tagged with
31 views

### Chordal Graph to Directed Acyclic Graph

I have seen an exercise which says an undirected graph $G=(V,E)$ is chordal if and only if the edges of $G$ can be oriented with directions, such that the resulting graph $D=(V,A)$ has the following ...
30 views

### Does “Let S be a minimal set of edge-disjoint chordal subgraphs of a graph G” make sense?

I have a graph $G$, and I would like to obtain a set $S$ of subgraphs of $G$ such that: every subgraph in $S$ is chordal; the subgraphs in $S$ are pairwise edge-disjoint; every triangle in $G$ is ...
133 views

### How to find the Maximum Clique number of a Chordal graph from Perfect elimination ordering?

For the past 2 days, I have been research on the web to try and understand and code how to find the Clique number of a chordal graph. I came to know that we need to use LexBFS to find the Perfect ...
58 views

### Treewidth of complete bipartite graph using chordal graph characterisation?

Compute the treewidth of $K_{m,n}$ if we know that $$tw(G)=\min \{\omega(H)-1 : G\subseteq H \ \wedge \ H \ \text{is chordal}\}$$ I know it should be $\min\{m,n\}$ but I do not know how to construct ...
39 views

### Are rectangle cover graphs chordal?

I am interested in the problem of covering (rectilinear) regions with rectangles that we can start to formulate in graph-theoretic terms as follows: Consider a region $V \subseteq S$ where $S$ is the ...
176 views

### Do all chordal graphs have simplicial decomposition?

If a graph is chordal, then it is a simple graph that contains no induced cycle of length 4 or more. A simplicial decomposition is a sequence ($V_1, V_2, ..., V_k$) of maximal cliques of $G$ such ...
I have a given planar chordal graph $G$. Due to the construction of $G$ I know that there exists at least one Hamiltonian cycle in $G$. My question is: How many Hamiltonian cycles are in $G$? (an ...