Introducing subclasses of basic chordal graphs

Basic chordal graphs arose when comparing clique trees of chordal graphs and compatible trees of dually chordal graphs. They were defined as those chordal graphs whose clique trees are exactly the compatible trees of its clique graph.In this work, we consider some subclasses of basic chordal graphs, like hereditary basic chordal graphs, basic DV and basic RDV graphs, we characterize them and we find some other properties they have, mostly involving clique graphs.     

Vertex partitions of chordal graphs

A k‐tree is a chordal graph with no (k + 2)‐clique. An ?‐tree‐partition of a graph G is a vertex partition of G into ‘bags,’ such that contracting each bag to a single vertex gives an ?‐tree (after deleting loops and replacing parallel edges by a single edge). We prove that for all k ≥ ? ≥ 0, every k‐tree has an ?‐tree‐partition in which each bag induces a connected ‐tree. An analogous result is proved for oriented k‐trees. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 167–172, 2006     

A new approach to chordal graphs

By a chordal graph is meant a graph with no induced cycle of length ⩾ 4. By a ternary system is meant an ordered pair (W, T), where W is a finite nonempty set, and T ⊆ W × W × W. Ternary systems satisfying certain axioms (A1)–(A5) are studied in this paper; note that these axioms can be formulated in a language of the first-order logic. For every finite nonempty set W, a bijective mapping from the set of all connected chordal graphs G with V(G) = W onto the set of all ternary systems (W, T) satisfying the axioms (A1)–(A5) is found in this paper.     

Independent domination in chordal graphs

A graph chordal if it does not contain any cycle of length greater than three as an induced subgraph. A set of S of vertices of a graph G = (V,E) is independent if not two vertices in S are adjacent, and is dominating if every vertex in V?S is adjacent to some vertex in S. We present a linear algorithm to locate a minimum weight independent dominating set in a chordal graph with 0–1 vertex weights.     

Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs

A locally connected spanning tree of a graph G is a spanning tree T of G such that the set of all neighbors of v in T induces a connected subgraph of G for every v∈V(G). The purpose of this paper is to give linear-time algorithms for finding locally connected spanning trees on strongly chordal graphs and proper circular-arc graphs, respectively.     

Obstructions to chordal circular-arc graphs of small independence number

A blocking quadruple (BQ) is a quadruple of vertices of a graph such that any two vertices of the quadruple either miss (have no neighbours on) some path connecting the remaining two vertices of the quadruple, or are connected by some path missed by the remaining two vertices. This is akin to the notion of asteroidal triple used in the classical characterization of interval graphs by Lekkerkerker and Boland [Klee, V., What are the intersection graphs of arcs in a circle?, American Mathematical Monthly 76 (1976), pp. 810–813.].In this note, we first observe that blocking quadruples are obstructions for circular-arc graphs. We then focus on chordal graphs, and study the relationship between the structure of chordal graphs and the presence/absence of blocking quadruples.Our contribution is two-fold. Firstly, we provide a forbidden induced subgraph characterization of chordal graphs without blocking quadruples. In particular, we observe that all the forbidden subgraphs are variants of the subgraphs forbidden for interval graphs [Klee, V., What are the intersection graphs of arcs in a circle?, American Mathematical Monthly 76 (1976), pp. 810–813.]. Secondly, we show that the absence of blocking quadruples is sufficient to guarantee that a chordal graph with no independent set of size five is a circular-arc graph. In our proof we use a novel geometric approach, constructing a circular-arc representation by traversing around a carefully chosen clique tree.     

Equivalences and the complete hierarchy of intersection graphs of paths in a tree

An (h,s,t)-representation of a graph G consists of a collection of subtrees of a tree T, where each subtree corresponds to a vertex in G, such that (i) the maximum degree of T is at most h, (ii) every subtree has maximum degree at most s, (iii) there is an edge between two vertices in the graph G if and only if the corresponding subtrees have at least t vertices in common in T. The class of graphs that have an (h,s,t)-representation is denoted by [h,s,t]. It is well known that the class of chordal graphs corresponds to the class [3, 3, 1]. Moreover, it was proved by Jamison and Mulder that chordal graphs correspond to orthodox-[3, 3, 1] graphs defined below.In this paper, we investigate the class of [h,2,t] graphs, i.e., the intersection graphs of paths in a tree. The [h,2,1] graphs are also known as path graphs [F. Gavril, A recognition algorithm for the intersection graphs of paths in trees, Discrete Math. 23 (1978) 211-227] or VPT graphs [M.C. Golumbic, R.E. Jamison, Edge and vertex intersection of paths in a tree, Discrete Math. 55 (1985) 151-159], and [h,2,2] graphs are known as the EPT graphs. We consider variations of [h,2,t] by three main parameters: h, t and whether the graph has an orthodox representation. We give the complete hierarchy of relationships between the classes of weakly chordal, chordal, [h,2,t] and orthodox-[h,2,t] graphs for varied values of h and t.     

Total coloring of planar graphs without chordal 7-cycles

A k-total-coloring of a graph G is a coloring of vertices and edges of G using k colors such that no two adjacent or incident elements receive the same color.In this paper,it is proved that if G is a planar graph with Δ(G) ≥ 7 and without chordal 7-cycles,then G has a(Δ(G) + 1)-total-coloring.     

Representing edge intersection graphs of paths on degree 4 trees

Let P be a collection of nontrivial simple paths on a host tree T. The edge intersection graph of P, denoted by EPT(P), has vertex set that corresponds to the members of P, and two vertices are joined by an edge if and only if the corresponding members of P share at least one common edge in T. An undirected graph G is called an edge intersection graph of paths in a tree if G=EPT(P) for some P and T. The EPT graphs are useful in network applications. Scheduling undirected calls in a tree network or assigning wavelengths to virtual connections in an optical tree network are equivalent to coloring its EPT graph.An undirected graph G is chordal if every cycle in G of length greater than 3 possesses a chord. Chordal graphs correspond to vertex intersection graphs of subtrees on a tree. An undirected graph G is weakly chordal if every cycle of length greater than 4 in G and in its complement possesses a chord. It is known that the EPT graphs restricted to host trees of vertex degree 3 are precisely the chordal EPT graphs. We prove a new analogous result that weakly chordal EPT graphs are precisely the EPT graphs with host tree restricted to degree 4. Moreover, this provides an algorithm to reduce a given EPT representation of a weakly chordal EPT graph to an EPT representation on a degree 4 tree. Finally, we raise a number of intriguing open questions regarding related families of graphs.     

The clique-separator graph for chordal graphs

We present a new representation of a chordal graph called the clique-separator graph, whose nodes are the maximal cliques and minimal vertex separators of the graph. We present structural properties of the clique-separator graph and additional properties when the chordal graph is an interval graph, proper interval graph, or split graph. We also characterize proper interval graphs and split graphs in terms of the clique-separator graph. We present an algorithm that constructs the clique-separator graph of a chordal graph in O(n³) time and of an interval graph in O(n²) time, where n is the number of vertices in the graph.     

Edge decompositions and rooted packings of graphs

Let H be a fixed graph. In this paper we consider the problem of edge decomposition of a graph into subgraphs isomorphic to H or $2K_2$ (a 2-edge matching). We give a partial classification of the problems of existence of such decomposition according to the computational complexity. More specifically, for some large class of graphs H we show that this problem is polynomial time solvable and for some other large class of graphs it is NP-complete. These results can be viewed as some edge decomposition analogs of a result by Loebl and Poljak who classified according to the computational complexity the problem of existence of a graph factor with components isomorphic to H or $K_2$. In the proofs of our results we apply so-called rooted packings into graphs which are mutual generalizations of both edge decompositions and factors of graphs.     

Intersection graphs of ideals of rings

In this paper, we consider the intersection graph G(R) of nontrivial left ideals of a ring R. We characterize the rings R for which the graph G(R) is connected and obtain several necessary and sufficient conditions on a ring R such that G(R) is complete. For a commutative ring R with identity, we show that G(R) is complete if and only if G(R[x]) is also so. In particular, we determine the values of n for which is connected, complete, bipartite, planar or has a cycle. Next, we characterize finite graphs which arise as the intersection graphs of and determine the set of all non-isomorphic graphs of for a given number of vertices. We also determine the values of n for which the graph of is Eulerian and Hamiltonian.     

Complexity of approximating the oriented diameter of chordal graphs

The oriented diameter of a bridgeless connected undirected (bcu) graph G is the smallest diameter among all the diameters of strongly connected orientations of G. We study algorithmic aspects of determining the oriented diameter of a chordal graph. We (a) construct a linear‐time approximation algorithm that, for a given chordal bcu graph G, finds a strongly connected orientation of G with diameter at most one plus twice the oriented diameter of G; (b) prove that, for every k ≥ 2 and k # 3, to decide whether a chordal (split for k = 2) bcu graph G admits an orientation of diameter k is NP‐complete; (c) show that, unless P = NP, there is neither a polynomial‐time absolute approximation algorithm nor an α‐approximation algorithm that computes the oriented diameter of a bcu chordal graph for α < . © 2004 Wiley Periodicals, Inc. J Graph Theory 45: 255–269, 2004     

On geodesic structures of weakly median graphs I. Decomposition and octahedral graphs

We prove that the non-trivial (finite or infinite) weakly median graphs which are undecomposable with respect to gated amalgamation and Cartesian multiplication are the 5-wheels, the subhyperoctahedra different from K₁, the path K_1,2 and the 4-cycle K_2,2, and the two-connected K₄- and K_1,1,3-free bridged graphs. These prime graphs are exactly the weakly median graphs which do not have any proper gated subgraphs other than singletons. For finite graphs, these results were already proved in [H.-J. Bandelt, V.C. Chepoi, The algebra of metric betweenness I: subdirect representation, retracts, and axiomatics of weakly median graphs, preprint, 2002]. A graph G is said to have the half-space copoint property (HSCP) if every non-trivial half-space of the geodesic convexity of G is a copoint at each of its neighbors. It turns out that any median graph has the HSCP. We characterize the weakly median graphs having the HSCP. We prove that the class of these graphs is closed under gated amalgamation and Cartesian multiplication, and we describe the prime and the finite regular elements of this class.     

Overlap number of graphs

An overlap representation of a graph G assigns sets to vertices so that vertices are adjacent if and only if their assigned sets intersect with neither containing the other. The overlap number φ(G) (introduced by Rosgen) is the minimum size of the union of the sets in such a representation. We prove the following: (1) An optimal overlap representation of a tree can be produced in linear time, and its size is the number of vertices in the largest subtree in which the neighbor of any leaf has degree 2. (2) If δ(G)?2 and G≠K₃, then φ(G)?|E(G)| ? 1, with equality when G is connected and triangle‐free and has no star‐cutset. (3) If G is an n‐vertex plane graph with n?5, then φ(G)?2n ? 5, with equality when every face has length 4 and there is no star‐cutset. (4) If G is an n‐vertex graph with n?14, then φ(G)?n²/4 ? n/2 ? 1, with equality for even n when G arises from K_{n/2, n/2} by deleting a perfect matching. © 2011 Wiley Periodicals, Inc. J Graph Theory