# 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.

14 questions
Filter by
Sorted by
Tagged with
52 views

I came up with the following conjecture: Let $G$ be a planar, biconnected chordal graph. Then there always exists a pair of adjacent vertices that have the same degree. Can someone find a counter ...
1 vote
28 views

### What is the necessary and sufficient condition for a graph to be a Hamiltonian Chordal Graphs?

Chordal Graph. 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. Hamiltonian ...
42 views

### Proof explanation: Every maximal clique of $G$ that contains no simplicial vertex of $G$ is a separating set of $G$ .

Let $G$ be a chordal graph with $n$ vertices. Then every maximal clique of $G$ that contains no simplicial vertex of $G$ is a separating set of $G$ . Proof: (induction on $n$) When $G = K_n$ , there ...
49 views

### Why does a chordal graph have induced cycles of length 3?

I understand that that is the definition. I think I am just not strong on the subject. What would happen if an induced cycle had, say, length 4?
12 views

### Is there any algorithm generating "all" chrodal graphs of order n?

I defined a procedure $\Gamma$ to generate graphs following some rules. The obtained graphs form a class of graphs $\mathcal{G}$. I found out that these graphs are chrodal. In the other hand, I ...
235 views

### Why are chordal graphs always perfect graphs?

Chordal graphs are always perfect graphs, but I am not sure exactly why. How does the chord make sure that the graph cant be imperfect?
1 vote
67 views

### Asking for proof: maximum k-colorable induced subgraph in an interval/chordal graph

Claim: Given any chordal graph $G(V,E)$, the following algorithm will find a maximum cardinality set $S\subseteq V$ such that the induced subgraph of $S$ is $k$-colorable. ...
151 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 ...
33 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 ...
1 vote
121 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 ...
47 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
323 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 ...