TY - JOUR
T1 - Claw-free graphs. II. Non-orientable prismatic graphs
AU - Chudnovsky, Maria
AU - Seymour, Paul
N1 - Funding Information:
E-mail addresses: [email protected] (M. Chudnovsky), [email protected] (P. Seymour). 1 This research was conducted while the author served as a Clay Mathematics Institute Research Fellow at Princeton University. 2 Supported by ONR grant N00014-01-1-0608 and NSF grant DMS-0070912.
PY - 2008/3
Y1 - 2008/3
N2 - A graph is prismatic if for every triangle T, every vertex not in T has exactly one neighbour in T. In a previous paper we gave a complete description of all 3-colourable prismatic graphs, and of a slightly more general class, the "orientable" prismatic graphs. In this paper we describe the non-orientable ones, thereby completing a description of all prismatic graphs. Since complements of prismatic graphs are claw-free, this is a step towards the main goal of this series of papers, providing a structural description of all claw-free graphs (a graph is claw-free if no vertex has three pairwise nonadjacent neighbours).
AB - A graph is prismatic if for every triangle T, every vertex not in T has exactly one neighbour in T. In a previous paper we gave a complete description of all 3-colourable prismatic graphs, and of a slightly more general class, the "orientable" prismatic graphs. In this paper we describe the non-orientable ones, thereby completing a description of all prismatic graphs. Since complements of prismatic graphs are claw-free, this is a step towards the main goal of this series of papers, providing a structural description of all claw-free graphs (a graph is claw-free if no vertex has three pairwise nonadjacent neighbours).
KW - Claw-free graphs
KW - Induced subgraphs
UR - http://www.scopus.com/inward/record.url?scp=38949204850&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=38949204850&partnerID=8YFLogxK
U2 - 10.1016/j.jctb.2007.06.006
DO - 10.1016/j.jctb.2007.06.006
M3 - Article
AN - SCOPUS:38949204850
SN - 0095-8956
VL - 98
SP - 249
EP - 290
JO - Journal of Combinatorial Theory. Series B
JF - Journal of Combinatorial Theory. Series B
IS - 2
ER -