Gallai graphs and anti-Gallai graphs (Q1126196): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 02:18, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Gallai graphs and anti-Gallai graphs |
scientific article |
Statements
Gallai graphs and anti-Gallai graphs (English)
0 references
22 June 1997
0 references
The Gallai graph \(\Gamma(G)\) and the anti-Gallai graph \(\Delta(G)\) of a graph \(G\) are spanning subgraphs of the line graph \(L(G)\) of \(G\). Both graphs have the edges of \(G\) as their vertices and two edges of \(G\) are adjacent vertices in \(\Gamma(G)\) if they are incident to a common vertex in \(G\) and if no triangle of \(G\) contains both edges. The edge set of \(\Delta(G)\) consists of all edges of \(L(G)\) not contained in \(\Gamma(G)\), i.e. two edges of \(G\) are adjacent vertices in \(\Delta(G)\) if there is a triangle in \(G\) containing both edges. The author presents a characterization of Gallai graphs and anti-Gallai graphs and he provides some properties and applications of such graphs. He proves that the four colour theorem is equivalent to the statement ``for each planar graph, the chromatic number and the clique number of its anit-Gallai graph are equal.'' Moreover, he verifies Berge's perfect graph conjecture (a graph is perfect if and only if it does not contain a cycle of odd length at least five or the complement of such a cycle as an induced subgraph) for anti-Gallai graphs and for a certain class of Gallai graphs and he presents a conjecture on Gallai graphs which is weaker than the perfect graph conjecture but stronger than the Lovász perfect graph theorem (a graph is perfect if and only if its complement is perfect). Finally, he proves that the problems of determining the clique number and the chromatic number of a Gallai graph are NP-complete.
0 references
Gallai graph
0 references
line graph
0 references
characterization
0 references
four colour theorem
0 references
clique number
0 references
perfect graph conjecture
0 references
chromatic number
0 references
NP-complete
0 references