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.

Filter by
Sorted by
Tagged with
2
votes
0answers
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 ...
2
votes
1answer
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
2answers
61 views

Number of Hamiltonian Cycles in planar chordal graph

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 ...
2
votes
0answers
40 views

conditions of a maximal planar graph to be chordal

what are the necessary and sufficient conditions of a maximal planar graph to be chordal? a maximal planar graph is a graph such that addition of one more edge results in non-planar graph. a chordal ...