Results 1 to 10 of about 905,601 (232)
Graphs of low chordality [PDF]
Discrete Mathematics & Theoretical Computer Science, 2005 The chordality of a graph with at least one cycle is the length of the longest induced cycle in it. The odd (even) chordality is defined to be the length of the longest induced odd (even) cycle in it. Chordal graphs have chordality at most 3. We show that co-circular-arc graphs and co-circle graphs have even chordality at most 4.
Sunil L Chandran +2 more
+10 more sources
Treewidth of Chordal Bipartite Graphs [PDF]
Journal of Algorithms, 1995 Summary: Chordal bipartite graphs are exactly those bipartite graphs in which every cycle of length at least six has a chord. The treewidth of a graph \(G\) is the smallest maximum cliquesize among all chordal supergraphs of \(G\) decreased by one.
Ton Kloks, Dieter Kratsch
openalex +8 more sources
Branchwidth of chordal graphs [PDF]
Discrete Applied Mathematics, 2009 This paper revisits the ‘branchwidth territories' of Kloks, Kratochvíl and Müller [T. Kloks, J. Kratochvíl, H. Müller, New branchwidth territories, in: 16th Ann. Symp. on Theoretical Aspect of Computer Science, STACS, in: Lecture Notes in Computer Science, vol. 1563, 1999, pp.
Christophe Paul, Jan Arne Telle
openalex +3 more sources
Discrete Mathematics, 1994 The authors characterize those multigraphs which are squares of chordal graphs and develop an algorithm for producing the unique square root from its squared chordal graph.
F. Harary, T. McKee
semanticscholar +2 more sources
The leafage of a chordal graph
Discussiones Mathematicae Graph Theory, 1998 The leafage l(G) of a chordal graph G is the minimum number of leaves of a tree in which G has an intersection representation by subtrees. We obtain upper and lower bounds on l(G) and compute it on special classes.
In-Jen Lin, T. McKee, D. West
semanticscholar +4 more sources
A Separator Theorem for Chordal Graphs [PDF]
SIAM Journal on Algebraic Discrete Methods, 1984 A graph is called chordal if every cycle of it of length at least four has a chord. In the paper it is proved: Let G be a chordal graph with n vertices and m edges. Then G has a set of O(\(\sqrt{m})\) vertices whose removal leaves no connected component with more than n/2 vertices.
John R. Gilbert +2 more
openalex +5 more sources
Chordal Completions of Planar Graphs
Journal of Combinatorial Theory, Series B, 1994 A graph is chordal if there are no induced cycles of length 4 or more. A chordal completion of a graph is formed by adding edges until the resulting graph is chordal. What is the minimal number of edges in a chordal completion? The authors answer this question for the class of planar graphs: every planar graph on \(n\) vertices has a chordal completion
Fan Chung, D. Mumford
openalex +3 more sources
Discrete Applied Mathematics, 2008 AbstractPolar graphs are a common generalization of bipartite, cobipartite, and split graphs. They are defined by the existence of a certain partition of vertices, which is NP-complete to decide for general graphs. It has been recently proved that for cographs, the existence of such a partition can be characterized by finitely many forbidden subgraphs,
Tınaz Ekim +3 more
openalex +3 more sources
Chordal multipartite graphs and chordal colorings
Discrete Mathematics, 2007 Abstract‘Chordal multipartite graphs’ are properly colored graphs such that two vertices in a minimal vertex separator are adjacent if and only if they are differently colored. They have induced cycle characterizations that transcend those of chordal and chordal bipartite graphs.
Terry A. McKee
openalex +3 more sources
How is a chordal graph like a supersolvable binary matroid? [PDF]
Discrete Mathematics, 2004 Raul Cordovil +2 more
openalex +2 more sources