Name
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. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1137/13091717X | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | Field | DocType |
circular-arc graph,chordal graph,asteroidal triple,forbidden subgraph characterization,Wiener index | Discrete mathematics,Combinatorics,Indifference graph,Interval graph,Lexicographic breadth-first search,Chordal graph,Treewidth,Pathwidth,Mathematics,Maximal independent set,Split graph | Journal |
Volume | Issue | ISSN |
28 | 2 | 0895-4801 |
Citations | PageRank | References |
1 | 0.36 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mathew C. Francis | 1 | 107 | 14.90 |
| Pavol Hell | 2 | 2638 | 288.75 |
| Juraj Stacho | 3 | 93 | 14.33 |