Premium
On greene's theorem for digraphs
Author(s) -
Hartman Irith BenArroyo,
Saleh Fathi,
Hershkowitz Daniel
Publication year - 1994
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190180208
Subject(s) - mathematics , combinatorics , conjecture , bipartite graph , cardinality (data modeling) , discrete mathematics , path (computing) , graph , computer science , data mining , programming language
Greene's Theorem states that the maximum cardinality of an optimal k ‐path in a poset is equal to the minimum k ‐norm of a k ‐optimal coloring. This result was extended to all acyclic digraphs, and is conjectured to hold for general digraphs. We prove the result for general digraphs in which an optimal k ‐path contains a path of cardinality one. This implies the validity of the conjecture for all bipartite digraphs. We also extend Greene's Theorem to all split graphs.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom