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
1
vote
1answer
22 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. ...
0
votes
0answers
10 views

Every chordal graph is formed by pasting complete subgraphs and vice versa

I want to prove that $G = (V,E)$ is chordal if and only if for some $\{V_\alpha\}_\alpha$ such that $V_\alpha \subset V$, we have that $E = \cup_\alpha V_\alpha \times V_\alpha$ where $V_\alpha \times ...
2
votes
0answers
79 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
32 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
1answer
78 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
42 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
251 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
78 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
1answer
54 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 ...