Meyniel weakly triangulated graphs. I: Co-perfect orderability

DOI10.1016/S0166-218X(96)00008-XMaRDI QIDQ678852zbMATH OpenOpenAlexFDO

Authors Ryan Hayward

Publication date 18 December 1997

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

Full work available at URL http://www.elsevier.com/locate/dam

zbMATH Keywords

chromatic numberconjecture of Chvátalgreedy algorithmpefectly orderableperfect orderweakly triangulated graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Review text

An algorithm is given that finds for any \(P_5\)-free weakly triangulated graph a perfect order in polynomial time. This proves a well-known conjecture of Chvátal that every \(P_5\)-free weakly triangulated graph is perfectly orderable. A graph is weakly triangulated if neither itself nor its complement contain a chordless cycle of length five or more. A graph is pefectly orderable if it has a perfect order, i.e. a linear order of the vertices such that for each induced ordered subgraph the number of colors used by the following greedy algorithm equals the chromatic number of the subgraph. The greedy algorithm is: given a linear order of the vertices of a graph, color the vertices in order, assigning to each the smallest positive integer (each integer representing a color) not assigned to any adjacent vertex already colored.

Recommendations

• A charming class of perfectly orderable graphs
• Four classes of perfectly orderable graphs
• On a conjecture of Hoàng and Tu concerning perfectly orderable graphs
• Weakly triangulated graphs

Cites work

• A charming class of perfectly orderable graphs
• Characterizations of totally balanced matrices
• On brittle graphs
• On the complexity of recognizing a class of perfectly orderable graphs
• On the complexity of recognizing perfectly orderable graphs
• On the perfect graph conjecture
• Weakly triangulated graphs
• Which line-graphs are perfectly orderable?

Cited in

(9)

• Coloring Artemis graphs
• A charming class of perfectly orderable graphs
• Weak order and descents for monotone triangles
• Weighted independent sets in classes of \(P_6\)-free graphs
• Finding houses and holes in graphs
• Perfectly contractile graphs and quadratic toric rings
• An \(O(nm)\)-time certifying algorithm for recognizing HHD-free graphs
• On a conjecture of Hoàng and Tu concerning perfectly orderable graphs
• A new characterization of HH-free graphs

This page was built for publication: Meyniel weakly triangulated graphs. I: Co-perfect orderability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q678852)