✦ LIBER ✦

On greene's theorem for digraphs

✍ Scribed by Irith Ben-Arroyo Hartman; Fathi Saleh; Daniel Hershkowitz

Publisher: John Wiley and Sons
Year: 1994
Tongue: English
Weight: 328 KB
Volume: 18
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190180208

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

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.

📜 SIMILAR VOLUMES

Meyniel's theorem for strongly (p, q) -

Meyniel's theorem for strongly (p, q) - Hamiltonian digraphs

✍ A. P. Wojda 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 134 KB

## Abstract We give the following theorem: Let __D__ = (__V, E__) be a strongly (__p__ + __q__ + 1)‐connected digraph with __n__ ≥ __p__ + __q__ + 1 vertices, where __p__ and __q__ are nonnegative integers, __p__ ≤ __n__ ‐ 2, __n__ ≥ 2. Suppose that, for each four vertices __u, v, w, z__ (not neces

On a Combinatorial Theorem of Curtis Gre

On a Combinatorial Theorem of Curtis Greene

✍ D. Maharam 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 66 KB

On a Theorem of J. A. Green

✍ Kenichi Yamauchi 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 117 KB

In this article we give another proof of the theorem concretely without using Frobenius's formula for induced characters and we also state some comments on Brauer's induction theorem. ᮊ 1998 Academic Press ## 1. Introduction Throughout this article, G, Z, and C denote a finite group, the ring of r

On Thompson's Theorem

✍ Lev Kazarin; Yakov Berkovich 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 138 KB

Let p be a prime divisor of the order of a finite group G. Thompson (1970, J. Algebra 14, 129-134) has proved the following remarkable result: a finite group G is p-nilpotent if the degrees of all its nonlinear irreducible characters are divisible by p (in fact, in that case G is solvable). In this

Cycles through Large Degree Vertices in

Cycles through Large Degree Vertices in Digraphs: A Generalization of Meyniel's Theorem

✍ Kenneth A. Berman; Xin Liu 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 191 KB

Let D=(V, E) be a digraph with vertex set V of size n and arc set E. For u # V, let d(u) denote the degree of u. A Meyniel set M is a subset of V such that d(u)+d(v) 2n&1 for every pair of nonadjacent vertices u and v belonging to M. In this paper we show that if D is strongly connected, then every

On Whitney's 2-isomorphism theorem for g

On Whitney's 2-isomorphism theorem for graphs

✍ K. Truemper 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 355 KB

## Abstract Let __G__ and __H__ be 2‐connected 2‐isomorphic graphs with __n__ nodes. Whitney's 2‐isomorphism theorem states that __G__ may be transformed to a graph __G__\* isomorphic to __H__ by repeated application of a simple operation, which we will term “switching”. We present a proof of Whitn