𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Coloring a graph optimally with two colors

✍ Scribed by H.J. Broersma; F. Göbel

Publisher
Elsevier Science
Year
1993
Tongue
English
Weight
536 KB
Volume
118
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Let G be a graph with point set V. A (2.)c,oloring of G is a map of V to ired, white!. An error occurs whenever the two endpoints of a line have the same color. An oprimul doring of G is a coloring of G for which the number of errors is minimum. The minimum number of errors is denoted by y(G), we derive upper and lower bounds for y(G) and prove that if G is a graph with n points and m lines, then max/0,m-~fn2J)~;'(G)~L~m-~(h(m)-l)J. where h(m)=min(nlm<(;)). The lower bound is sharp, and for infinitely many values of no the upper bound is attained for all sufficiently large n.

📜 SIMILAR VOLUMES

Interval edge coloring of a graph with f
Interval edge coloring of a graph with forbidden colors
✍ Marek Kubale 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 596 KB

## This paper is complementary to Kubale (1989). We consider herein a problem of interval coloring the edges of a graph under the restriction that certain colors cannot be used for some edges. We give lower and upper bounds on the minimum number of colors required for such a coloring. Since the ge

Coloring graphs with locally few colors
Coloring graphs with locally few colors
✍ P Erdös; Z Füredi; A Hajnal; P Komjáth; V Rödl; Á Seress 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 832 KB

Let G be a graph, m > r t> 1 integers. Suppose that it has a good-coloring with m colors which uses at most r colors in the neighborhood of every vertex. We investigate these so-called local r-colorings. One of our results (Theorem 2.4) states: The chromatic number of G, Chr(G) ~< r2" log21og2 m (an

Optimal edge coloring of large graphs
Optimal edge coloring of large graphs
✍ G�mez, J.; Escudero, M. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 95 KB 👁 3 views

Most of the general families of large considered graphs in the context of the so-called (⌬, D) problem-that is, how to obtain graphs with maximum order, given their maximum degree ⌬ and their diameter D-known up to now for any value of ⌬ and D, are obtained as product graphs, compound graphs, and ge

Optimal acyclic edge-coloring of cubic g
Optimal acyclic edge-coloring of cubic graphs
✍ Lars Døvling Andersen; Edita Máčajová;; Ján Mazák 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 194 KB

An __acyclic edge‐coloring__ of a graph is a proper edge‐coloring such that the subgraph induced by the edges of any two colors is acyclic. The __acyclic chromatic index__ of a graph __G__ is the smallest number of colors in an acyclic edge‐coloring of __G__. We prove that the acyclic chromatic inde