Meyniel weakly triangulated graphs. I: Co-perfect orderability (Q678852): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 10:25, 30 January 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