Partial characterizations of circle graphs

A circle graph is the intersection graph of a family of chords on a circle. There is no known characterization of circle graphs by forbidden induced subgraphs that do not involve the notions of local equivalence or pivoting operations. We characterize circle graphs by a list of minimal forbidden induced subgraphs when the graph belongs to one of the following classes: linear domino graphs, P₄-tidy graphs, and tree-cographs. We also completely characterize by minimal forbidden induced subgraphs the class of unit Helly circle graphs, which are those circle graphs having a model whose chords have all the same length, are pairwise different, and satisfy the Helly property.     

Self-clique Helly circular-arc graphs

A clique in a graph is a complete subgraph maximal under inclusion. The clique graph of a graph is the intersection graph of its cliques. A graph is self-clique when it is isomorphic to its clique graph. A circular-arc graph is the intersection graph of a family of arcs of a circle. A Helly circular-arc graph is a circular-arc graph admitting a model whose arcs satisfy the Helly property. In this note, we describe all the self-clique Helly circular-arc graphs.     

The clique operator on circular-arc graphs

A circular-arc graphG is the intersection graph of a collection of arcs on the circle and such a collection is called a model of G. Say that the model is proper when no arc of the collection contains another one, it is Helly when the arcs satisfy the Helly Property, while the model is proper Helly when it is simultaneously proper and Helly. A graph admitting a Helly (resp. proper Helly) model is called a Helly (resp. proper Helly) circular-arc graph. The clique graphK(G) of a graph G is the intersection graph of its cliques. The iterated clique graphKⁱ(G) of G is defined by K⁰(G)=G and Kⁱ⁺¹(G)=K(Kⁱ(G)). In this paper, we consider two problems on clique graphs of circular-arc graphs. The first is to characterize clique graphs of Helly circular-arc graphs and proper Helly circular-arc graphs. The second is to characterize the graph to which a general circular-arc graph K-converges, if it is K-convergent. We propose complete solutions to both problems, extending the partial results known so far. The methods lead to linear time recognition algorithms, for both problems.     

Orientations of circle graphs

Let C(v₁, …,v_n) be a system consisting of a circle C with chords v₁, …,v_n on it having different endpoints. Define a graph G having vertex set V(G) = {v₁, …,v_n} and for which vertices v_i and v_j are adjacent in G if the chords v_i and v_j intersect. Such a graph will be called a circle graph. The chords divide the interior of C into a number of regions. We give a method which associates to each such region an orientation of the edges of G. For a given C(v₁, …,v_n) the number m of different orientations corresponding to it satisfies q + 1 ≤ m ≤ n + q + 1, where q is the number of edges in G. An oriented graph obtained from a diagram C(v₁, …,v_n) as above is called an oriented circle graph (OCG). We show that transitive orientations of permutation graphs are OCGs, and give a characterization of tournaments which are OCGs. When the region is a peripheral one, the orientation of G is acyclic. In this case we define a special orientation of the complement of G, and use this to develop an improved algorithm for finding a maximum independent set in G.     

On constructible graphs,locally Helly graphs,and convexity

A (finite or infinite) graph G is constructible if there exists a well‐ordering ≤ of its vertices such that for every vertex x which is not the smallest element, there is a vertex y < x which is adjacent to x and to every neighbor z of x with z < x. Particular constructible graphs are Helly graphs and connected bridged graphs. In this paper we study a new class of constructible graphs, the class of locally Helly graphs. A graph G is locally Helly if, for every pair (x,y) of vertices of G whose distance is d ≥ 2, there exists a vertex whose distance to x is d ? 1 and which is adjacent to y and to all neighbors of y whose distance to x is at most d. Helly graphs are locally Helly, and the converse holds for finite graphs. Among different properties we prove that a locally Helly graph is strongly dismantable, hence cop‐win, if and only if it contains no isometric rays. We show that a locally Helly graph G is finitely Helly, that is, every finite family of pairwise non‐disjoint balls of G has a non‐empty intersection. We give a sufficient condition by forbidden subgraphs so that the three concepts of Helly graphs, of locally Helly graphs and of finitely Helly graphs are equivalent. Finally, generalizing different results, in particular those of Bandelt and Chepoi 1 about Helly graphs and bridged graphs, we prove that the Helly number h(G) of the geodesic convexity in a constructible graph G is equal to its clique number ω(G), provided that ω(G) is finite. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 280–298, 2003     

Homotopy type of circle graph complexes motivated by extreme Khovanov homology

It was proven by González-Meneses, Manchón and Silvero that the extreme Khovanov homology of a link diagram is isomorphic to the reduced (co)homology of the independence simplicial complex obtained from a bipartite circle graph constructed from the diagram. In this paper, we conjecture that this simplicial complex is always homotopy equivalent to a wedge of spheres. In particular, its homotopy type, if not contractible, would be a link invariant (up to suspension), and it would imply that the extreme Khovanov homology of any link diagram does not contain torsion. We prove the conjecture in many special cases and find it convincing to generalize it to every circle graph (intersection graph of chords in a circle). In particular, we prove it for the families of cactus, outerplanar, permutation and non-nested graphs. Conversely, we also give a method for constructing a permutation graph whose independence simplicial complex is homotopy equivalent to any given finite wedge of spheres. We also present some combinatorial results on the homotopy type of finite simplicial complexes and a theorem shedding light on previous results by Csorba, Nagel and Reiner, Jonsson and Barmak. We study the implications of our results to knot theory; more precisely, we compute the real-extreme Khovanov homology of torus links T(3, q) and obtain examples of H-thick knots whose extreme Khovanov homology groups are separated either by one or two gaps as long as desired.     

Algorithms for clique-independent sets on subclasses of circular-arc graphs

A circular-arc graph is the intersection graph of arcs on a circle. A Helly circular-arc graph is a circular-arc graph admitting a model whose arcs satisfy the Helly property. A clique-independent set of a graph is a set of pairwise disjoint cliques of the graph. It is NP-hard to compute the maximum cardinality of a clique-independent set for a general graph. In the present paper, we propose polynomial time algorithms for finding the maximum cardinality and weight of a clique-independent set of a -free CA graph. Also, we apply the algorithms to the special case of an HCA graph. The complexity of the proposed algorithm for the cardinality problem in HCA graphs is O(n). This represents an improvement over the existing algorithm by Guruswami and Pandu Rangan, whose complexity is O(n²). These algorithms suppose that an HCA model of the graph is given.     

Associativity in multiary quasigroups: the way of biased expansions

A multiary (polyadic, n-ary) quasigroup is an n-ary operation which is invertible with respect to each of its variables. A biased expansion of a graph is a kind of branched covering graph with an additional structure similar to the combinatorial homotopy of circles. A biased expansion of a circle with chords encodes a multiary quasigroup, the chords corresponding to factorizations, i.e., associative structure. Some but not all biased expansions are constructed from groups (group expansions); these include all biased expansions of complete graphs (with at least four nodes), which correspond to Dowling’s lattices of a group and encode an iterated group operation. We show that any biased expansion of a 3-connected graph (with at least four nodes) is a group expansion, and that all 2-connected biased expansions are constructed by the identification of edges from group expansions and irreducible multiary quasigroups. If a 2-connected biased expansion covers every base edge at most three times, or if every four-node minor that contains a fixed edge is a group expansion, then the whole biased expansion is a group expansion. We deduce that if a multiary quasigroup has a factorization graph that is 3-connected, or if every ternary principal retract is an iterated group isotope, it is isotopic to an iterated group. We mention applications of generalizing Dowling geometries and of transversal designs of high strength.     

Absolute retracts of bipartite graphs

A bipartite graph G is an absolute retract if every isometric embedding g of G into a bipartite graph H is a coretraction (that is, there exists an edge-preserving map h from H to G such that hg is the identity map on G). Examples of absolute retracts are provided by chordal bipartite graphs and the covering graphs of modular lattices of breadth two. We give a construction and several characterizations of bipartite absolute retracts involving Helly type conditions. Bipartite absolute retracts apply to competitive location theory: they are precisely those bipartite graphs on which locational equilibria (Condorcet solutions) always exist.All graphs in this paper are finite, connected, and without loops or multiple edges.     

On circle graphs with girth at least five

Circle graphs with girth at least five are known to be 2-degenerate [A.A. Ageev, Every circle graph with girth at least 5 is 3-colourable, Discrete Math. 195 (1999) 229-233]. In this paper, we prove that circle graphs with girth at least g≥5 and minimum degree at least two contain a chain of g−4 vertices of degree two, which implies Ageev’s result in the case g=5. We then use this structural property to give an upper bound on the circular chromatic number of circle graphs with girth at least g≥5 as well as a precise estimate of their maximum average degree.     

Partial Characterizations of Circular-Arc Graphs

A circular-arc graph is the intersection graph of a family of arcs on a circle. A characterization by forbidden induced subgraphs for this class of graphs is not known, and in this work we present a partial result in this direction. We characterize circular-arc graphs by a list of minimal forbidden induced subgraphs when the graph belongs to the following classes: diamond-free graphs, P₄-free graphs, paw-free graphs, and claw-free chordal graphs.     

Deterministic “Snakes and Ladders” Heuristic for the Hamiltonian cycle problem

We present a polynomial complexity, deterministic, heuristic for solving the Hamiltonian cycle problem (HCP) in an undirected graph of order $n$ . Although finding a Hamiltonian cycle is not theoretically guaranteed, we have observed that the heuristic is successful even in cases where such cycles are extremely rare, and it also performs very well on all HCP instances of large graphs listed on the TSPLIB web page. The heuristic owes its name to a visualisation of its iterations. All vertices of the graph are placed on a given circle in some order. The graph’s edges are classified as either snakes or ladders, with snakes forming arcs of the circle and ladders forming its chords. The heuristic strives to place exactly $n$ snakes on the circle, thereby forming a Hamiltonian cycle. The Snakes and Ladders Heuristic uses transformations inspired by $k$ -opt algorithms such as the, now classical, Lin–Kernighan heuristic to reorder the vertices on the circle in order to transform some ladders into snakes and vice versa. The use of a suitable stopping criterion ensures the heuristic terminates in polynomial time if no improvement is made in $n^3$ major iterations.     

Hamiltonian connectedness in 3-connected line graphs

We investigate graphs G such that the line graph L(G) is hamiltonian connected if and only if L(G) is 3-connected, and prove that if each 3-edge-cut contains an edge lying in a short cycle of G, then L(G) has the above mentioned property. Our result extends Kriesell’s recent result in [M. Kriesell, All 4-connected line graphs of claw free graphs are hamiltonian-connected, J. Combin. Theory Ser. B 82 (2001) 306-315] that every 4-connected line graph of a claw free graph is hamiltonian connected. Another application of our main result shows that if L(G) does not have an hourglass (a graph isomorphic to K₅−E(C₄), where C₄ is an cycle of length 4 in K₅) as an induced subgraph, and if every 3-cut of L(G) is not independent, then L(G) is hamiltonian connected if and only if κ(L(G))≥3, which extends a recent result by Kriesell [M. Kriesell, All 4-connected line graphs of claw free graphs are hamiltonian-connected, J. Combin. Theory Ser. B 82 (2001) 306-315] that every 4-connected hourglass free line graph is hamiltonian connected.     

Polygon-circle and word-representable graphs

We describe work on the relationship between the independently-studied polygon-circle graphs and word-representable graphs.A graph G = (V, E) is word-representable if there exists a word w over the alpha-bet V such that letters x and y form a subword of the form xyxy ⋯ or yxyx ⋯ iff xy is an edge in E. Word-representable graphs generalise several well-known and well-studied classes of graphs [S. Kitaev, A Comprehensive Introduction to the Theory of Word-Representable Graphs, Lecture Notes in Computer Science 10396 (2017) 36–67; S. Kitaev, V. Lozin, “Words and Graphs”, Springer, 2015]. It is known that any word-representable graph is k-word-representable, that is, can be represented by a word having exactly k copies of each letter for some k dependent on the graph. Recognising whether a graph is word-representable is NP-complete ([S. Kitaev, V. Lozin, “Words and Graphs”, Springer, 2015, Theorem 4.2.15]). A polygon-circle graph (also known as a spider graph) is the intersection graph of a set of polygons inscribed in a circle [M. Koebe, On a new class of intersection graphs, Ann. Discrete Math. (1992) 141–143]. That is, two vertices of a graph are adjacent if their respective polygons have a non-empty intersection, and the set of polygons that correspond to vertices in this way are said to represent the graph. Recognising whether an input graph is a polygon-circle graph is NP-complete [M. Pergel, Recognition of polygon-circle graphs and graphs of interval filaments is NP-complete, Graph-Theoretic Concepts in Computer Science: 33rd Int. Workshop, Lecture Notes in Computer Science, 4769 (2007) 238–247]. We show that neither of these two classes is included in the other one by showing that the word-representable Petersen graph and crown graphs are not polygon-circle, while the non-word-representable wheel graph W₅ is polygon-circle. We also provide a more refined result showing that for any k ≥ 3, there are k-word-representable graphs which are neither (k −1)-word-representable nor polygon-circle.     

An edge-deletion problem for locally finite graphs

For each positive integer n, let T_n be the tree in which exactly one vertex has degree n and all the other vertices have degree n + 1. A graph G is called stable if its edge set is nonempty and if deleting an arbitrary edge of G there is always a component of the residue graph which is isomorphic to G. The question whether there are locally finite stable graphs that are not isomorphic to one of the graphs T_n is answered affirmatively by constructing an uncountable family of pairwise nonisomorphic, locally finite, stable graphs. Further, the following results are proved: (1) Among the locally finite trees containing no subdivision of T₂, the oneway infinite path T₁ is the only stable graph. (2) Among the locally finite graphs containing no two-way infinite path, T₁ is also the only stable graph.     

Characterizations for co-graphs defined by restricted NLC-width or clique-width operations

In this paper we characterize subclasses of co-graphs defined by restricted NLC-width operations and subclasses of co-graphs defined by restricted clique-width operations.We show that a graph has NLCT-width 1 if and only if it is (C₄,P₄)-free. Since (C₄,P₄)-free graphs are exactly trivially perfect graphs, the set of graphs of NLCT-width 1 is equal to the set of trivially perfect graphs, and a recursive definition for trivially perfect graphs follows. Further we show that a graph has linear NLC-width 1 if and only if is (C₄,P₄,2K₂)-free. This implies that the set of graphs of linear NLC-width 1 is equal to the set of threshold graphs.We also give forbidden induced subgraph characterizations for co-graphs defined by restricted clique-width operations using P₄, 2K₂, and co-2P₃.     

A class of h-perfect graphs

A graph is said to be h-perfect if the convex hull of its independent sets is defined by the constraints corresponding to cliques and odd holes, and the nonnegativity constraints. Series-parallel graphs and perfect graphs are h-perfect. The purpose of this paper is to extend the class of graphs known to be h-perfect. Thus, given a graph which is the union of a bipartite graph G₁ and a graph G₂ having exactly two common nodes a and b, and no edge in common, we prove that G is h-perfect if so is the graph obtained from G by replacing G₁ by an a-b chain (the length of which depends on G₁). This result enables us to prove that the graph obtained by substituting bipartite graphs for edges of a series-parallel graph is h-perfect, and also that the identification of two nodes of a bipartite graph yields an h-perfect graph (modulo a reduction which preserves h-perfection).     

Extending partial representations of circle graphs

The partial representation extension problem is a recently introduced generalization of the recognition problem. A circle graph is an intersection graph of chords of a circle. We study the partial representation extension problem for circle graphs, where the input consists of a graph and a partial representation giving some predrawn chords that represent an induced subgraph of . The question is whether one can extend to a representation of the entire graph , that is, whether one can draw the remaining chords into a partially predrawn representation to obtain a representation of . Our main result is an time algorithm for partial representation extension of circle graphs, where is the number of vertices. To show this, we describe the structure of all representations of a circle graph using split decomposition. This can be of independent interest.     

Path factors and parallel knock-out schemes of almost claw-free graphs

An H₁,{H₂}-factor of a graph G is a spanning subgraph of G with exactly one component isomorphic to the graph H₁ and all other components (if there are any) isomorphic to the graph H₂. We completely characterise the class of connected almost claw-free graphs that have a P₇,{P₂}-factor, where P₇ and P₂ denote the paths on seven and two vertices, respectively. We apply this result to parallel knock-out schemes for almost claw-free graphs. These schemes proceed in rounds in each of which each surviving vertex eliminates one of its surviving neighbours. A graph is reducible if such a scheme eliminates every vertex in the graph. Using our characterisation, we are able to classify all reducible almost claw-free graphs, and we can show that every reducible almost claw-free graph is reducible in at most two rounds. This leads to a quadratic time algorithm for determining if an almost claw-free graph is reducible (which is a generalisation and improvement upon the previous strongest result that showed that there was a O(n^5.376) time algorithm for claw-free graphs on n vertices).