✦ LIBER ✦

Bounded vertex colorings of graphs

✍ Scribed by Pierre Hansen; Alain Hertz; Julio Kuplinsky

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 503 KB
Volume: 111
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(93)90165-p

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Some new bounds for the maximum number o

Some new bounds for the maximum number of vertex colorings of a (v,e)-graph

✍ Byer, Owen D. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 126 KB 👁 3 views

Let f (v, e, λ) denote the maximum number of proper vertex colorings of a graph with v vertices and e edges in λ colors. In this paper we present some new upper bounds for f (v, e, λ). In particular, a new notion of pseudoproper colorings of a graph is given, which allows us to significantly improve

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

Polychromatic colorings of bounded degre

Polychromatic colorings of bounded degree plane graphs

✍ Elad Horev; Roi Krakovski 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 289 KB

## Abstract A __polychromatic k__‐__coloring__ of a plane graph __G__ is an assignment of __k__ colors to the vertices of __G__ such that every face of __G__ has __all k__ colors on its boundary. For a given plane graph __G__, one seeks the __maximum__ number __k__ such that __G__ admits a polychro

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

On a theorem about vertex colorings of g

On a theorem about vertex colorings of graphs

✍ Claudio Bernardi 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 121 KB

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.

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