The Library
Blocking quadruple : a new obstruction to circular-arc graphs
Tools
Francis, Mathew, Hell, Pavol and Stacho, Juraj (2014) Blocking quadruple : a new obstruction to circular-arc graphs. SIAM Journal on Discrete Mathematics, Volume 28 (Number 2). pp. 631-655. doi:10.1137/13091717X ISSN 0895-4801.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1137/13091717X
Abstract
Finding a forbidden subgraph characterization of circular-arc graphs is a challenging open problem. Many partial results toward this goal have been proposed over the years, but a satisfactory answer has so far eluded us. In this paper, we suggest a new direction in this line of research. We propose a novel structural obstruction to circular-arc graphs---a blocking quadruple---and study its use in characterizing circular-arc graphs within chordal graphs. Notably, we observe that the absence of blocking quadruples unifies characterizations of various known chordal subclasses of circular-arc graphs found in the literature. To this end, we provide a forbidden induced subgraph characterization of chordal graphs without blocking quadruples and show that the absence of blocking quadruples exactly characterizes chordal circular-arc graphs of independence number 4 or less. Our proof uses an interesting geometric approach, constructing a circular-arc representation by traversing around a carefully chosen clique tree. In fact, we prove that this characterizes circular-arc representability of all chordal graphs.
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||
Journal or Publication Title: | SIAM Journal on Discrete Mathematics | ||||||||
Publisher: | Society for Industrial and Applied Mathematics | ||||||||
ISSN: | 0895-4801 | ||||||||
Official Date: | 10 April 2014 | ||||||||
Dates: |
|
||||||||
Volume: | Volume 28 | ||||||||
Number: | Number 2 | ||||||||
Page Range: | pp. 631-655 | ||||||||
DOI: | 10.1137/13091717X | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |