In the work [𝒪(m⋅ n) algorithms for the recognition and isomorphism problems on circular-arc graphs, SIAM J. Comput. 24(3), 411-439, (1995)], Wen-Lian Hsu claims three results concerning the class of circular-arc graphs: - the design of so-called decomposition trees that represent the structure of all normalized intersection models of circular-arc graphs, - an 𝒪(nm)-time recognition algorithm for circular-arc graphs, - an 𝒪(nm)-time isomorphism algorithm for circular-arc graphs. In [Discrete Math. Theor. Comput. Sci., 15(1), 157-182, 2013] Curtis, Lin, McConnell, Nussbaum, Soulignac, Spinrad, and Szwarcfiter showed that Hsu’s isomorphism algorithm is incorrect. In this note, we show that the other two results - namely, the construction of decomposition trees and the recognition algorithm - are also flawed. We also present the main ideas that made it possible to construct a data structure that maintains normalized models of circular-arc graphs.

In a graph G, a k-attack A is any set of at most k vertices and l-defense D is a set of at most l vertices. We say that defense D counters attack A if each a in A can be matched to a distinct defender d in D with a equal to d or a adjacent to d in G. In the defensive domination problem, we are interested in deciding, for a graph G and positive integers k and l given on input, if there exists an l-defense that counters every possible k-attack on G. Defensive domination is a natural resource allocation problem and can be used to model network robustness and security, disaster response strategies, and redundancy designs. The defensive domination problem is naturally in the complexity class $Σ^P_2$. The problem was known to be NP-hard in general, and polynomial-time algorithms were found for some restricted graph classes. In this note we prove that the defensive domination problem is $Σ^P_2$-complete. We also introduce a natural variant of the defensive domination problem in which the defense is allowed to be a multiset of vertices. This variant is also $Σ^P_2$-complete, but we show that it admits a polynomial-time algorithm in the class of interval graphs. A similar result was known for the original setting in the class of proper interval graphs.

In 1992 Biró, Hujter and Tuza introduced, for every fixed connected graph $H$, the class of $H$-graphs, defined as the intersection graphs of connected subgraphs of some subdivision of $H$. Recently, quite a lot of research has been devoted to understanding the tractability border for various computational problems, such as recognition or isomorphism testing, in classes of $H$-graphs for different graphs $H$. In this work we undertake this research topic, focusing on the recognition problem. Chaplick, Töpfer, Voborn\'ık, and Zeman showed, for every fixed tree $T$, a polynomial-time algorithm recognizing $T$-graphs. Tucker showed a polynomial time algorithm recognizing $K_3$-graphs (circular-arc graphs). On the other hand, Chaplick at al. showed that recognition of $H$-graphs is $NP$-hard if $H$ contains two different cycles sharing an edge. The main two results of this work narrow the gap between the $NP$-hard and $P$ cases of $H$-graphs recognition. First, we show that recognition of $H$-graphs is $NP$-hard when $H$ contains two different cycles. On the other hand, we show a polynomial-time algorithm recognizing $L$-graphs, where $L$ is a graph containing a cycle and an edge attached to it ($L$-graphs are called lollipop graphs). Our work leaves open the recognition problems of $M$-graphs for every unicyclic graph $M$ different from a cycle and a lollipop. Other results of this work, which shed some light on the cases that remain open, are as follows. Firstly, the recognition of $M$-graphs, where $M$ is a fixed unicyclic graph, admits a polynomial time algorithm if we restrict the input to graphs containing particular holes (hence recognition of $M$-graphs is probably most difficult for chordal graphs). Secondly, the recognition of medusa graphs, which are defined as the union of $M$-graphs, where $M$ runs over all unicyclic graphs, is $NP$-complete.

Abstract A grounded L-graph is the intersection graph of a collection of “L” shapes whose topmost points belong to a common horizontal line. We prove that every grounded L-graph with clique number $$\omega $$ ω has chromatic number at most $$17\omega ^4$$ 17 ω 4 . This improves the doubly-exponential bound of McGuinness and generalizes the recent result that the class of circle graphs is polynomially $$\chi $$ χ -bounded. We also survey $$\chi $$ χ -boundedness problems for grounded geometric intersection graphs and give a high-level overview of recent techniques to obtain polynomial bounds.

Abstract A permutation graph can be defined as an intersection graph of segments whose endpoints lie on two parallel lines $$\ell _1$$ ℓ 1 and $$\ell _2$$ ℓ 2 , one on each. A bipartite permutation graph is a permutation graph which is bipartite. In this paper we study the parameterized complexity of the bipartite permutation vertex deletion problem, which asks, for a given n-vertex graph, whether we can remove at most k vertices to obtain a bipartite permutation graph. This problem is $$\mathsf {NP}$$ NP -complete by the classical result of Lewis and Yannakakis [20]. We analyze the structure of the so-called almost bipartite permutation graphs which may contain holes (large induced cycles) in contrast to bipartite permutation graphs. We exploit the structural properties of the shortest hole in a such graph. We use it to obtain an algorithm for the bipartite permutation vertex deletion problem with running time $${\mathcal {O}}(9^k \cdot n^9)$$ O ( 9 k · n 9 ) , and also give a polynomial-time 9-approximation algorithm.

Curve pseudo-visibility graphs generalize polygon and pseudo-polygon visibility graphs and form a hereditary class of graphs. We prove that every curve pseudo-visibility graph with clique number ω has chromatic number at most 3⋅4^{ω-1}. The proof is carried through in the setting of ordered graphs; we identify two conditions satisfied by every curve pseudo-visibility graph (considered as an ordered graph) and prove that they are sufficient for the claimed bound. The proof is algorithmic: both the clique number and a colouring with the claimed number of colours can be computed in polynomial time.

For a graph G, a function $$\psi $$ is called a bar visibility representation of G when for each vertex $$v \in V(G)$$ , $$\psi (v)$$ is a horizontal line segment (bar) and $$uv \in E(G)$$ iff there is an unobstructed, vertical, $$\varepsilon $$ -wide line of sight between $$\psi (u)$$ and $$\psi (v)$$ . Graphs admitting such representations are well understood (via simple characterizations) and recognizable in linear time. For a directed graph G, a bar visibility representation $$\psi $$ of G, additionally, for each directed edge (u, v) of G, puts the bar $$\psi (u)$$ strictly below the bar $$\psi (v)$$ . We study a generalization of the recognition problem where a function $$\psi '$$ defined on a subset $$V'$$ of V(G) is given and the question is whether there is a bar visibility representation $$\psi $$ of G with $$\psi |V' = \psi '$$ . We show that for undirected graphs this problem together with closely related problems are $$\mathsf {NP}$$ -complete, but for certain cases involving directed graphs it is solvable in polynomial time.

Recently, it was proved that triangle-free intersection graphs of $$n$$ line segments in the plane can have chromatic number as large as $$\Theta (\log \log n)$$ . Essentially the same construction produces $$\Theta (\log \log n)$$ -chromatic triangle-free intersection graphs of a variety of other geometric shapes—those belonging to any class of compact arc-connected sets in $$\mathbb {R}^2$$ closed under horizontal scaling, vertical scaling, and translation, except for axis-parallel rectangles. We show that this construction is asymptotically optimal for intersection graphs of boundaries of axis-parallel rectangles, which can be alternatively described as overlap graphs of axis-parallel rectangles. That is, we prove that triangle-free rectangle overlap graphs have chromatic number $$O(\log \log n)$$ , improving on the previous bound of $$O(\log n)$$ . To this end, we exploit a relationship between off-line coloring of rectangle overlap graphs and on-line coloring of interval overlap graphs. Our coloring method decomposes the graph into a bounded number of subgraphs with a tree-like structure that “encodes” strategies of the adversary in the on-line coloring problem. Then, these subgraphs are colored with $$O(\log \log n)$$ colors using a combination of techniques from on-line algorithms (first-fit) and data structure design (heavy-light decomposition).

Several classical constructions illustrate the fact that the chromatic number of a graph may be arbitrarily large compared to its clique number. However, until very recently no such construction was known for intersection graphs of geometric objects in the plane. We provide a general construction that for any arc-connected compact set $$X$$ in $$\mathbb{R }^2$$ that is not an axis-aligned rectangle and for any positive integer $$k$$ produces a family $$\mathcal{F }$$ of sets, each obtained by an independent horizontal and vertical scaling and translation of $$X$$ , such that no three sets in $$\mathcal{F }$$ pairwise intersect and $$\chi (\mathcal{F })>k$$ . This provides a negative answer to a question of Gyárfás and Lehel for L-shapes. With extra conditions we also show how to construct a triangle-free family of homothetic (uniformly scaled) copies of a set with arbitrarily large chromatic number. This applies to many common shapes, like circles, square boundaries or equilateral L-shapes. Additionally, we reveal a surprising connection between coloring geometric objects in the plane and on-line coloring of intervals on the line.

One of the simplest heuristics for obtaining a proper coloring of a graph is the first-fit algorithm. First-fit visits each vertex of the graph in the specified order and assigns to every point the least possible number. Let $\mathcal{G}$ be a class of incomparability graphs with bounded maximum clique size, closed under taking induced subgraphs. We prove that first-fit uses a bounded number of colors on the graphs in $\mathcal{G}$ iff there is an incomparability graph of clique size $2$ not contained in $\mathcal{G}$.

The main question in the on-line chain partitioning problem is to determine whether there exists an algorithm that partitions on-line posets of width at most w into polynomial number of chains see Trotter's chapter Partially ordered sets in the Handbook of Combinatorics. So far the best known on-line algorithm of Kierstead used at most (5ω- 1)/4 chains; on the other hand Szemeredi proved that any on-line algorithm requires at least (ω+1/2) chains. These results were obtained in the early eighties and since then no progress in the general case has been done. We provide an on-line algorithm that partitions orders of width ω into at most ω16 log ωchains. This yields the first subexponential upper bound for on-line chain partitioning problem.

We consider a problem of partitioning a partially ordered set into chains by first-fit algorithm. In general this algorithm uses arbitrarily many chains on a class of bounded width posets. In this paper we prove that First-Fit uses at most $3tw^2$ chains to partition any poset of width w which does not induce two incomparable chains of height t. In this way we get a wide class of posets with polynomial bound for the on-line chain partitioning problem. We also discuss some consequences of our result for coloring graphs by First-Fit.