# Vertebrate interval graphs

@article{Jiang2021VertebrateIG, title={Vertebrate interval graphs}, author={Rain Jiang and Kai Jiang and Minghui Jiang}, journal={ArXiv}, year={2021}, volume={abs/2109.12140} }

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 ≥ 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, when v = 2, whether a vertebrate interval graph can be partitioned into two proper interval graphs can be decided in polynomial time.

#### Figures from this paper

#### References

SHOWING 1-10 OF 14 REFERENCES

Trivially perfect graphs

- Computer Science, Mathematics
- Discret. Math.
- 1978

The trivially perfect graphs are characterized as a proper subclass of the triangulated graphs (thus disproving a claim of Buneman 3), and they are related to some well-known classes of perfect graphs. Expand

Partitioning an interval graph into subgraphs with small claws

- Computer Science, Mathematics
- ArXiv
- 2021

A simple approximation algorithm for partitioning an interval graph into the minimum number of induced subgraphs with claw number at most v is presented, with approximation ratio 3 when 1 ≤ v ≤ 2, and 2 when v ≥ 3. Expand

The subchromatic number of a graph

- Mathematics, Computer Science
- Discret. Math.
- 1989

The subchromatic number X S ( G ) of a graph G = ( V, E ) is the smallest order k of a partition {V 1 , V 2 , …, V k } of the vertices V ( G ) such that the subgraph ( V i ) induced by each subset V… Expand

More About Subcolorings

- Computer Science, Mathematics
- Computing
- 2002

A number of results on the combinatorics, the algorithmics, and the complexity of subcolorings are derived, including asymptotically best possible upper bounds on the subchromatic number of interval graphs, chordal graphs, and permutation graphs in terms of the number of vertices. Expand

The complexity of G-free colourability

- Computer Science, Mathematics
- Discret. Math.
- 1997

It is shown that for any graph G on more than two vertices the problem is NP-complete, equivalent to having a bipartition of the vertex set where each cell is K2-free. Expand

Cubicity of Interval Graphs and the Claw Number

- Mathematics, Computer Science
- Electron. Notes Discret. Math.
- 2009

This paper shows that for an interval graph G, cub ( G ) ⩽ ⌈ log 2 α ⌉ , where α is the independence number of G, and defines claw number ψ ( G) to be the largest positive integer m such that S ( m ) is an induced subgraph of G. Expand

Vertex-Partitioning into Fixed Additive Induced-Hereditary Properties is NP-hard

- Mathematics, Computer Science
- Electron. J. Comb.
- 2004

If ${cal P} and ${\cal Q}$ are additive induced-hereditary graph properties, then $({\cal P}, {\cal Q})$-colouring is NP-hard, with the sole exception of graph $2$- Colouring (the case where both P and Q are the set of finite edgeless graphs). Expand

A short proof that 'proper = unit'

- Computer Science, Mathematics
- Discret. Math.
- 1999

Abstract A short proof is given that the graphs with proper interval representations are the same as the graphs with unit interval representations.