Line perfect graphs

DOI10.1007/BF01593791zbMath0366.05043OpenAlexW1994363553WikidataQ56388864 ScholiaQ56388864MaRDI QIDQ4141848

Leslie E. jun. Trotter

Publication date: 1977

Published in: Mathematical Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01593791

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (05C99)

Related Items (33)

Intersection graphs of paths in a tree ⋮ Neighbourhood-perfect line graphs ⋮ On edge perfectness and classes of bipartite graphs ⋮ Open shop scheduling with some additional constraints ⋮ Identifying Codes in Line Graphs ⋮ Polyhedral characterizations and perfection of line graphs ⋮ Gallai graphs and anti-Gallai graphs ⋮ Graphical properties related to minimal imperfection ⋮ Minimum weighted clique cover on claw‐free perfect graphs ⋮ Toric rings of perfectly matchable subgraph polytopes ⋮ A note on chromatic properties of threshold graphs ⋮ On completely positive graphs and their complements ⋮ Dominoes ⋮ Classes of perfect graphs ⋮ Almost nonpreemptive schedules ⋮ Completely positive matrices. ⋮ Bicolored matchings in some classes of graphs ⋮ Bicolored matchings in some classes of graphs ⋮ Characterization of completely positive graphs ⋮ Mutual exclusion scheduling with interval graphs or related classes. II ⋮ Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs ⋮ Unnamed Item ⋮ A class of facet producing graphs for vertex packing polyhedra ⋮ On minimal forbidden subgraph characterizations of balanced graphs ⋮ On line perfect graphs ⋮ Partial characterizations of coordinated graphs: Line graphs and complements of forests ⋮ A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles ⋮ On minimal forbidden subgraph characterizations of balanced graphs ⋮ Packing paths perfectly ⋮ Counting Weighted Independent Sets beyond the Permanent ⋮ The edge intersection graphs of paths in a tree ⋮ Graph imperfection. I ⋮ \((p,k)\)-coloring problems in line graphs

Cites Work

• The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
• On certain polytopes associated with graphs
• Anti-blocking polyhedra
• A characterization of perfect graphs
• Normal hypergraphs and the perfect graph conjecture
• Establishing the matching polytope
• Paths, Trees, and Flowers
• Maximum matching and a polyhedron with 0,1-vertices
• Blocking and anti-blocking pairs of polyhedra
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Line perfect graphs