Gallai graphs and anti-Gallai graphs

DOI10.1016/0012-365X(95)00109-AzbMath0864.05031OpenAlexW2081455745MaRDI QIDQ1126196

Van Bang Le

Publication date: 22 June 1997

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(95)00109-a

zbMATH Keywords

characterizationline graphchromatic numberclique numberNP-completeGallai graphperfect graph conjecturefour colour theorem

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15)

Related Items (18)

Spectrum of Gallai graph of some graphs ⋮ Subgraph distances in graphs defined by edge transfers ⋮ Small edge sets meeting all triangles of a graph ⋮ Gallai and anti-Gallai graph operators ⋮ Triangle packings and transversals of some \(K_{4}\)-free graphs ⋮ Generalized line graphs: Cartesian products and complexity of recognition ⋮ Maximizing the strong triadic closure in split graphs and proper interval graphs ⋮ On the hardness of recognizing triangular line graphs ⋮ Forests and trees among Gallai graphs ⋮ EULERIAN AND HAMILTONIAN PROPERTIES OF GALLAI AND ANTI-GALLAI TOTAL GRAPHS ⋮ Spectrum of anti-Gallai graph of some graphs ⋮ Triangular line graphs and word sense disambiguation ⋮ On the relation of strong triadic closure and cluster deletion ⋮ 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 ⋮ Unnamed Item ⋮ On an edge partition and root graphs of some classes of line graphs ⋮ A survey of the studies on Gallai and anti-Gallai graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Duality and perfection for edges in cliques
• Topics on perfect graphs
• \(K_ i\)-covers. I: Complexity and polytopes
• Two classes of perfect graphs
• Recognizing claw-free perfect graphs
• The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
• Critical perfect graphs and perfect 3-chromatic graphs
• Mortality of iterated Gallai graphs
• Iterated \(k\)-line graphs
• Two characterizations of interchange graphs of complete m-partite graphs
• Ki-covers. II.Ki-perfect graphs
• The NP-Completeness of Edge-Coloring
• Line perfect graphs
• Perfect k‐line graphs and k‐total graphs
• Transitiv orientierbare Graphen

This page was built for publication: Gallai graphs and anti-Gallai graphs