The Library
On 2-subcolourings of chordal graphs
Tools
Stacho, Juraj (2008) On 2-subcolourings of chordal graphs. In: LATIN 2008 : Theoretical Informatics, Búzios, Brazil,, 7-11 Apr 2008. Published in: LATIN 2008: Theoretical Informatics, Vol.4957 pp. 544-554. ISBN 9783540787723 . doi:10.1007/978-3-540-78773-0_47
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.1007/978-3-540-78773-0_47
Abstract
A 2-subcolouring of a graph is a partition of the vertices into two subsets, each inducing a P 3-free graph, i.e., a disjoint union of cliques. We give the first polynomial time algorithm to test whether a chordal graph has a 2-subcolouring. This solves (for two colours) an open problem of Broersma, Fomin, Nešetřil, and Woeginger, who gave an O(n 5) time algorithm for interval graphs. Our algorithm for the larger class of chordal graphs has complexity only O(n 3).
Item Type: | Conference Item (Paper) | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Journal or Publication Title: | LATIN 2008: Theoretical Informatics | ||||
Publisher: | Springer New York LLC | ||||
ISBN: | 9783540787723 | ||||
Book Title: | LATIN 2008: Theoretical Informatics | ||||
Official Date: | 2008 | ||||
Dates: |
|
||||
Volume: | Vol.4957 | ||||
Page Range: | pp. 544-554 | ||||
DOI: | 10.1007/978-3-540-78773-0_47 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Conference Paper Type: | Paper | ||||
Title of Event: | LATIN 2008 : Theoretical Informatics | ||||
Type of Event: | Conference | ||||
Location of Event: | Búzios, Brazil, | ||||
Date(s) of Event: | 7-11 Apr 2008 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |