✦ LIBER ✦

On a theorem about vertex colorings of graphs

✍ Scribed by Claudio Bernardi

Publisher: Elsevier Science
Year: 1987
Tongue: English
Weight: 121 KB
Volume: 64
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(87)90243-3

No coin nor oath required. For personal study only.

✦ Synopsis

Lawrence [2, Theorem 3] and Borodin and Kostochka [1, Lemma 2' 1 both give the same theorem about vertex colorings of graphs (Corollary 1 below). But Lawrence's proof, although powerful, is a little long, and Borodin and Kostoehka state the result without a proof.

📜 SIMILAR VOLUMES

Some applications of Vizing's theorem to

Some applications of Vizing's theorem to vertex colorings of graphs

✍ Henry A. Kierstead; James H. Schmerl 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 812 KB

In this paper we shall study the relationships between the following three families of assertions: C(n): If G is a graph that does not induce & or KS-e and w(G) 6 n. then x(G)rn+l. C'(n): If M is a multigraph such that A(M)< n, p(M)<2 and M does not contain a S-sided triangle (i.e., a triangle with

Bounded vertex colorings of graphs

✍ Pierre Hansen; Alain Hertz; Julio Kuplinsky 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 503 KB

Vertex-distinguishing edge colorings of

Vertex-distinguishing edge colorings of graphs

✍ P. N. Balister; O. M. Riordan; R. H. Schelp 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 136 KB 👁 1 views

On the Vertex-Distinguishing Proper Edge

On the Vertex-Distinguishing Proper Edge-Colorings of Graphs

✍ Cristina Bazgan; Amel Harkat-Benhamdine; Hao Li; Mariusz Woźniak 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 189 KB

We prove the conjecture of Burris and Schelp: a coloring of the edges of a graph of order n such that a vertex is not incident with two edges of the same color and any two vertices are incident with different sets of colors is possible using at most n+1 colors. 1999 Academic Press ## 1. Introducti

Vertex colorings of graphs without short

Vertex colorings of graphs without short odd cycles

✍ Andrzej Dudek; Reshma Ramadurai 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 118 KB 👁 1 views

Motivated by the work of Nešetřil and R ödl on "Partitions of vertices" we are interested in obtaining some quantitative extensions of their result. In particular, given a natural number r and a graph G of order m with odd girth g, we show the existence of a graph H with odd girth at least g and ord

Note on the reconstruction of vertex col

Note on the reconstruction of vertex colored graphs

✍ R. Taylor 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 164 KB 👁 2 views