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
3 votes
1 answer
52 views

Conjecture about chordal graphs

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 ...
user avatar
1 vote
0 answers
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 ...
user avatar
  • 1,174
0 votes
1 answer
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 ...
user avatar
0 votes
0 answers
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?
user avatar
0 votes
0 answers
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 ...
user avatar
2 votes
1 answer
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?
user avatar
1 vote
1 answer
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. ...
user avatar
  • 37
2 votes
0 answers
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 ...
user avatar
2 votes
1 answer
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 ...
user avatar
  • 79
1 vote
1 answer
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 ...
user avatar
2 votes
1 answer
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 ...
user avatar
  • 123
1 vote
1 answer
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 ...
user avatar
  • 241
0 votes
2 answers
107 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 ...
user avatar
  • 308
2 votes
1 answer
84 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 ...
user avatar
  • 331