Gallai graphs and anti-Gallai graphs

DOI10.1016/0012-365X(95)00109-AMaRDI QIDQ1126196zbMATH OpenOpenAlexFDO

Authors 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

chromatic numberline graphcharacterizationclique numberNP-completeGallai graphperfect graph conjecturefour colour theorem

Mathematics Subject Classification ID

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

Recommendations

• 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

Cites work

• 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?)
• Critical perfect graphs and perfect 3-chromatic graphs
• Duality and perfection for edges in cliques
• 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
• \(K_ i\)-covers. I: Complexity and polytopes

Cited in

(24)

• On an edge partition and root graphs of some classes of line graphs
• Forests and trees among Gallai graphs
• Generalized line graphs: Cartesian products and complexity of recognition
• The Gallai and anti-Gallai graphs of strongly regular graphs
• Spectrum of Gallai graph of some graphs
• Triangular line graphs and word sense disambiguation
• Triangle packings and transversals of some \(K_{4}\)-free graphs
• Bounds for the eigenvalues of Gallai graphs of some graphs
• On the hardness of recognizing triangular line graphs
• Gallai and anti-Gallai graphs of a graph
• Maximizing the strong triadic closure in split graphs and proper interval graphs
• EULERIAN AND HAMILTONIAN PROPERTIES OF GALLAI AND ANTI-GALLAI TOTAL GRAPHS
• Maximizing the strong triadic closure in split graphs and proper interval graphs
• A survey of the studies on Gallai and anti-Gallai graphs
• Cycles and complete \(k\)-partite graphs among Gallai graphs
• Strong triadic closure in cographs and graphs of low maximum degree
• Spectrum of anti-Gallai graph of some graphs
• Small edge sets meeting all triangles of a graph
• Gallai and anti-Gallai graph operators
• Subgraph distances in graphs defined by edge transfers
• P-antiregular graphs
• Gallai's question and constructions of almost hypotraceable graphs
• Your rugby mates don't need to know your colleagues: triadic closure with edge colors
• scientific article; zbMATH DE number 5911880 (Why is no real title available?)

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)