Claw-free graphs. I: Orientable prismatic graphs (Q2384800): Difference between revisions
From MaRDI portal
Removed claims |
ReferenceBot (talk | contribs) Changed an Item |
||
(3 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: P. D. Seymour / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Ralph J. Faudree / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.jctb.2007.02.002 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2036700147 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Claw-free graphs. II: Non-orientable prismatic graphs / rank | |||
Normal rank |
Revision as of 09:47, 27 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Claw-free graphs. I: Orientable prismatic graphs |
scientific article |
Statements
Claw-free graphs. I: Orientable prismatic graphs (English)
0 references
10 October 2007
0 references
The overall objective of the authors is to give a characterization of claw-free graphs (graphs that do not have an induced \(K_{1,3}\) subgraph). A graph \(G\) is prismatic if for each triangle \(T\), every vertex in \(G\) not in \(T\) has exactly one neighbor in \(T\). The complement of a prismatic graph is a claw-free graph, so a characterization of prismatic graphs is one step in the characterization of claw-free graphs. A prismatic graph is orientable if each of the triangles has an orientation and these orientations on disjoint triangles are compatible with the matching that exists between the triangles. It is shown that every \(3\)-colorable prismatic graph is orientable. A characterization of \(3\)-colorable prismatic graphs is given by showing that such graphs admit a decomposition (called a worn chain decomposition) with each of the terms coming from one of three classes of graphs of \(3\)-colorable graphs \({\mathcal Q}_0\), \({\mathcal Q}_1\), and \({\mathcal Q}_2\). The graphs in \({\mathcal Q}_0\) have no triangles, the graphs in \({\mathcal Q}_1\) are isomorphic to the line graphs of \(K_{3,3}\), and the graphs in \({\mathcal Q}_2\) are a canonically-colored path of triangle graphs.
0 references
Claw-free graphs
0 references
Prismatic
0 references
Structure theorem
0 references