On partitioning interval graphs into proper interval subgraphs and related problems | Zendy

Gardi Frédéric | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

On partitioning interval graphs into proper interval subgraphs and related problems

Author(s) -

Gardi Frédéric

Publication year - 2011

Publication title -

journal of graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.164

H-Index - 54

eISSN - 1097-0118

pISSN - 0364-9024

DOI - 10.1002/jgt.20539

Subject(s) - mathematics , combinatorics , partition (number theory) , interval graph , constructive , discrete mathematics , interval (graph theory) , graph , graph partition , pathwidth , line graph , computer science , process (computing) , operating system

In this paper, we establish that any interval graph (resp. circular‐arc graph) with n vertices admits a partition into at most ⌈log 3 n ⌉ (resp. ⌈log 3 n ⌉ + 1) proper interval subgraphs, for n >1. The proof is constructive and provides an efficient algorithm to compute such a partition. On the other hand, this bound is shown to be asymptotically sharp for an infinite family of interval graphs. In addition, some results are derived for related problems. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:38‐54, 2011

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research