Gallai graphs and anti-Gallai graphs
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.
- A survey of the studies on Gallai and anti-Gallai graphs
- Some conjectures on perfect graphs
- Cycles and complete \(k\)-partite graphs among Gallai graphs
- Two classes of perfect graphs
- Gallai and anti-Gallai graph operators
- A note on perfect graphs
- On an edge partition and root graphs of some classes of line graphs
- Generalized line graphs: Cartesian products and complexity of recognition
- scientific article; zbMATH DE number 3869356
- scientific article; zbMATH DE number 1789914
- \(K_ i\)-covers. I: Complexity and polytopes
- Critical perfect graphs and perfect 3-chromatic graphs
- Duality and perfection for edges in cliques
- scientific article; zbMATH DE number 3724488 (Why is no real title available?)
- scientific article; zbMATH DE number 42695 (Why is no real title available?)
- scientific article; zbMATH DE number 3522018 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 851097 (Why is no real title available?)
- Iterated k-line graphs
- Ki-covers. II.Ki-perfect graphs
- Line perfect graphs
- Mortality of iterated Gallai graphs
- Perfect k‐line graphs and k‐total graphs
- Recognizing claw-free perfect graphs
- The NP-Completeness of Edge-Coloring
- The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
- Topics on perfect graphs
- Transitiv orientierbare Graphen
- Two characterizations of interchange graphs of complete m-partite graphs
- Two classes of perfect graphs
- Subgraph distances in graphs defined by edge transfers
- Gallai's question and constructions of almost hypotraceable graphs
- Small edge sets meeting all triangles of a graph
- Maximizing the strong triadic closure in split graphs and proper interval graphs
- Spectrum of anti-Gallai graph of some graphs
- Triangular line graphs and word sense disambiguation
- Gallai and anti-Gallai graph operators
- Triangle packings and transversals of some \(K_{4}\)-free graphs
- scientific article; zbMATH DE number 5911880 (Why is no real title available?)
- P-antiregular graphs
- Gallai and anti-Gallai graphs of a graph
- On the hardness of recognizing triangular line graphs
- Forests and trees among Gallai graphs
- A survey of the studies on Gallai and anti-Gallai graphs
- On an edge partition and root graphs of some classes of line graphs
- Maximizing the strong triadic closure in split graphs and proper interval graphs
- EULERIAN AND HAMILTONIAN PROPERTIES OF GALLAI AND ANTI-GALLAI TOTAL GRAPHS
- Cycles and complete \(k\)-partite graphs among Gallai graphs
- Strong triadic closure in cographs and graphs of low maximum degree
- Your rugby mates don't need to know your colleagues: triadic closure with edge colors
- Bounds for the eigenvalues of Gallai graphs of some graphs
- The Gallai and anti-Gallai graphs of strongly regular graphs
- Revisit the coloring problem of Gallai graphs
- Spectrum of Gallai graph of some graphs
- Generalized line graphs: Cartesian products and complexity of recognition
This page was built for publication: Gallai graphs and anti-Gallai graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1126196)
