Meyniel weakly triangulated graphs. I: Co-perfect orderability (Q678852): Difference between revisions
From MaRDI portal
Changed an Item |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Characterizations of totally balanced matrices / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Which line-graphs are perfectly orderable? / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Weakly triangulated graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the complexity of recognizing a class of perfectly orderable graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On brittle graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A charming class of perfectly orderable graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the perfect graph conjecture / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the complexity of recognizing perfectly orderable graphs / rank | |||
Normal rank |
Revision as of 12:20, 27 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Meyniel weakly triangulated graphs. I: Co-perfect orderability |
scientific article |
Statements
Meyniel weakly triangulated graphs. I: Co-perfect orderability (English)
0 references
18 December 1997
0 references
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.
0 references
weakly triangulated graph
0 references
perfect order
0 references
conjecture of Chvátal
0 references
pefectly orderable
0 references
greedy algorithm
0 references
chromatic number
0 references