✦ LIBER ✦

Colorful induced subgraphs

✍ Scribed by H.A. Kierstead; W.T. Trotter

Publisher: Elsevier Science
Year: 1992
Tongue: English
Weight: 302 KB
Volume: 101
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(92)90600-k

No coin nor oath required. For personal study only.

✦ Synopsis

A colored graph is a graph whose vertices have been properly, though not necessarily optimally colored, with integers. Colored graphs have a natural orientation in which edges are directed from the end point with smaller color to the end point with larger color. A subgraph of a colored graph is colorful if each of its vertices has a distinct color. We prove that there exists a function f (k, n) such that for any colored graph G, if x(G) > f (w(G), n) then G induces either a colorful out directed star with n leaves or a colorful directed path on n vertices. We also show that this result would be false if either alternative was omitted. Our results provide a solution to Problem 115. Discrete Math. 79.

📜 SIMILAR VOLUMES

Coloring with three-colored subgraphs

✍ Dhruv Mubayi 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 75 KB

## 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 expli

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

✍ 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

COLORING SUBGRAPHS OF THE RADO GRAPH

✍ N. W. Sauer* 📂 Article 📅 2006 🏛 Springer-Verlag 🌐 English ⚖ 300 KB

Large induced degenerate subgraphs

✍ N. Alon; J. Kahn; P. D. Seymour 📂 Article 📅 1987 🏛 Springer Japan 🌐 English ⚖ 558 KB

Maximumk-regular induced subgraphs

✍ Domingos M. Cardoso; Marcin Kamiński; Vadim Lozin 📂 Article 📅 2007 🏛 Springer US 🌐 English ⚖ 291 KB