Results 1 to 10 of about 12,294 (276)
Edge erasures and chordal graphs [PDF]
Electronic Journal of Graph Theory and Applications, 2021 We prove several results about chordal graphs and weighted chordal graphs by focusing on exposed edges. These are edges that are properly contained in a single maximal complete subgraph.
Jared Culbertson +2 more
doaj +4 more sources
The Neighborhood Polynomial of Chordal Graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2022 We study the neighborhood polynomial and the complexity of its computation for chordal graphs. The neighborhood polynomial of a graph is the generating function of subsets of its vertices that have a common neighbor.
Helena Bergold +2 more
doaj +3 more sources
Capturing Logarithmic Space and Polynomial Time on Chordal Claw-Free Graphs [PDF]
Logical Methods in Computer Science, 2019 We show that the class of chordal claw-free graphs admits LREC$_=$-definable canonization. LREC$_=$ is a logic that extends first-order logic with counting by an operator that allows it to formalize a limited form of recursion.
Berit Grußien
doaj +3 more sources
Discrete Mathematics & Theoretical Computer Science, 2019 Slimness of a graph measures the local deviation of its metric from a tree metric. In a graph $G=(V,E)$, a geodesic triangle $\bigtriangleup(x,y,z)$ with $x, y, z\in V$ is the union $P(x,y) \cup P(x,z) \cup P(y,z)$ of three shortest paths connecting ...
Feodor F. Dragan, Abdulhakeem Mohammed
doaj +3 more sources
The leafage of a chordal graph [PDF]
, 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.
Lin, In-Jen +2 more
core +4 more sources
Recognition of chordal graphs and cographs which are Cover-Incomparability graphs [PDF]
Discrete Mathematics & Theoretical Computer ScienceCover-Incomparability graphs (C-I graphs) are an interesting class of graphs from posets. A C-I graph is a graph from a poset $P=(V,\le)$ with vertex set $V$, and the edge-set is the union of edge sets of the cover graph and the incomparability graph of ...
Arun Anil, Manoj Changat
doaj +3 more sources
Chordal Graphs are Fully Orientable [PDF]
, 2012 Suppose that D is an acyclic orientation of a graph G. An arc of D is called dependent if its reversal creates a directed cycle. Let m and M denote the minimum and the maximum of the number of dependent arcs over all acyclic orientations of G.
Lai, Hsin-Hao, Lih, Ko-Wei
core +3 more sources
Componentwise linearity of ideals arising from graphs [PDF]
Le Matematiche, 2008 Let G be a simple undirected graph on n vertices.
Veronica Crispin, Eric Emtander
doaj +4 more sources
Backbone colouring of chordal graphs
Procedia Computer ScienceA proper $k$-colouring of a graph $G=(V,E)$ is a function $c: V(G)\to \{1,\ldots,k\}$ such that $c(u)\neq c(v)$ for every edge $uv\in E(G)$. The chromatic number $χ(G)$ is the minimum $k$ such that there exists a proper $k$-colouring of $G$. Given a spanning subgraph $H$ of $G$, a $q$-backbone $k$-colouring of $(G,H)$ is a proper $k$-colouring $c$ of ...
Júlio Aráujo +2 more
openalex +5 more sources