Gallai graphs and anti-Gallai graphs (Q1126196): Difference between revisions

From MaRDI portal
RedirectionBot (talk | contribs)
Changed an Item
Import240304020342 (talk | contribs)
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
    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
    0 references

    Identifiers