𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Coloring with three-colored subgraphs

✍ Scribed by Dhruv Mubayi

Publisher
John Wiley and Sons
Year
2003
Tongue
English
Weight
75 KB
Volume
42
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Let f(n) be the minimum number of colors required to color the edges of K~n,n~ such that every copy of K~3,3~ receives at least three colors on its edges. We prove that

$$(0.62+o(1))\sqrt{n}< , f(n)< , (1+o(1))\sqrt{n}$$,

where the upper bound is obtained by an explicit edge‐coloring. This complements earlier results of Axenovich, Füredi, and Mubayi [1]. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 193–198, 2003

📜 SIMILAR VOLUMES

Maximum k-colorable subgraphs
Maximum k-colorable subgraphs
✍ S. C. Locke 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 303 KB

## Abstract A lower bound is established on the number of edges in a maximum __k__‐colorable subgraph of a loopless graph __G__. For the special case of 3‐regular graphs, lower bounds are also determined on the maximum number of edges in a bipartite subgraph whose color classes are of equal size.

Subgraph-avoiding coloring of graphs
Subgraph-avoiding coloring of graphs
✍ Jia Shen 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB

## Abstract Given a “forbidden graph” __F__ and an integer __k__, an __F‐avoiding k‐coloring__ of a graph __G__ is a __k__‐coloring of the vertices of __G__ such that no maximal __F__‐free subgraph of __G__ is monochromatic. The __F‐avoiding chromatic number__ __ac__~__F__~(__G__) is the smallest i

Maximum Δ-edge-colorable subgraphs of cl
Maximum Δ-edge-colorable subgraphs of class II graphs
✍ Vahan V. Mkrtchyan; Eckhard Steffen 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 180 KB

## Abstract A graph __G__ is class II, if its chromatic index is at least Δ + 1. Let __H__ be a maximum Δ‐edge‐colorable subgraph of __G__. The paper proves best possible lower bounds for |__E__(__H__)|/|__E__(__G__)|, and structural properties of maximum Δ‐edge‐colorable subgraphs. It is shown tha

cover
Loved With Color
✍ M. K. Moore 📂 Fiction 📅 2019 🏛 Breeding Nation Publishing 🌐 English ⚖ 34 KB
Coloring of trees with minimum sum of co
Coloring of trees with minimum sum of colors
✍ Jiang, Tao; West, Douglas B. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 227 KB

The chromatic sum of a graph is the smallest sum of colors among all proper colorings with natural numbers. The strength is the minimum number of colors needed to achieve the chromatic sum. We construct for each positive integer k a tree with strength k that has maximum degree only 2k -2. The result