Results 1 to 10 of about 333,465 (75)

Coloring and Recognizing Directed Interval Graphs [PDF]

, 2023
A \emph{mixed interval graph} is an interval graph that has, for every pair of intersecting intervals, either an arc (directed arbitrarily) or an (undirected) edge. We are particularly interested in scenarios where edges and arcs are defined by the geometry of intervals.
arxiv   +1 more source

Maximum Cut on Interval Graphs of Interval Count Two is NP-complete [PDF]

arXiv, 2022
An interval graph has interval count $\ell$ if it has an interval model, where among every $\ell+1$ intervals there are two that have the same length. Maximum Cut on interval graphs has been found to be NP-complete recently by Adhikary et al. while deciding its complexity on unit interval graphs (graphs with interval count one) remains a longstanding ...
arxiv  

Signed interval graphs and bigraphs: A generalization of interval graphs and bigraphs [PDF]

arXiv, 2022
In this paper, we define and characterize signed interval graphs and bigraphs introducing the concept of negative interval. Also we have shown that these classes of graphs are respectively a generalization of well known classes of interval graphs and interval bigraphs.
arxiv  

U-Bubble Model for Mixed Unit Interval Graphs and its Applications: The MaxCut Problem Revisited [PDF]

Algorithmica 83(12), 3649-3680 (2021), 2020
Interval graphs, intersection graphs of segments on a real line (intervals), play a key role in the study of algorithms and special structural properties. Unit interval graphs, their proper subclass, where each interval has a unit length, has also been extensively studied.
arxiv   +1 more source

On the Maximum Cardinality Cut Problem in Proper Interval Graphs and Related Graph Classes [PDF]

arXiv, 2020
Although it has been claimed in two different papers that the maximum cardinality cut problem is polynomial-time solvable for proper interval graphs, both of them turned out to be erroneous. In this paper, we give FPT algorithms for the maximum cardinality cut problem in classes of graphs containing proper interval graphs and mixed unit interval graphs
arxiv  

Stability of Critical p-Improper Interval Graphs [PDF]

Congressus Numerantium, 2017, Volume 228, 2019
A $p$-improper interval graph is an interval graph that has an interval representation in which no interval contains more than $p$ other intervals. A critical $p$-improper interval graph is $p-1$ improper when any vertex is removed. In this paper we investigate the spectrum of impropriety of critical $p$-improper interval graphs upon the removal of a ...
arxiv  

Vertebrate interval graphs [PDF]

arXiv, 2021
A vertebrate interval graph is an interval graph in which the maximum size of a set of independent vertices equals the number of maximal cliques. For any fixed $v \ge 1$, there is a polynomial-time algorithm for deciding whether a vertebrate interval graph admits a vertex partition into two induced subgraphs with claw number at most $v$. In particular,
arxiv  

The minimum linear arrangement problem on proper interval graphs [PDF]

arXiv, 2006
We present a linear time algorithm for the minimum linear arrangement problem on proper interval graphs.
arxiv  

Improper Interval Graphs and the Corresponding Minimal Forbidden Interval Subgraphs [PDF]

arXiv, 2015
An interval graph is considered improper if and only if it has a representation such that an interval contains another interval. Previously these have been investigated in terms of balance and minimal forbidden interval subgraphs for the class of 1-improper interval graphs.
arxiv  

Bounded Representations of Interval and Proper Interval Graphs [PDF]

arXiv, 2013
Klavik et al. [arXiv:1207.6960] recently introduced a generalization of recognition called the bounded representation problem which we study for the classes of interval and proper interval graphs. The input gives a graph G and in addition for each vertex v two intervals L_v and R_v called bounds.
arxiv