𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Subgraph-avoiding coloring of graphs

✍ Scribed by Jia Shen

Publisher
John Wiley and Sons
Year
2009
Tongue
English
Weight
115 KB
Volume
63
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 integer k such that G is F‐avoiding k‐colorable. In this paper, we will give a complete answer to the following question: for which graph F, does there exist a constant C, depending only on F, such that ac~F~(G) ⩽ C for any graph G? For those graphs F with unbounded avoiding chromatic number, upper bounds for ac~F~(G) in terms of various invariants of G are also given. Particularly, we prove that \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${{ac}}_{{{F}}}({{G}})\le {{2}}\lceil\sqrt{{{n}}}\rceil+{{1}}$\end{document}, where n is the order of G and F is not K~k~ or \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}$\overline{{{K}}_{{{k}}}}$\end{document}. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 300–310, 2010

📜 SIMILAR VOLUMES

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

Star coloring of graphs
Star coloring of graphs
✍ Guillaume Fertin; André Raspaud; Bruce Reed 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 181 KB

## Abstract A __star coloring__ of an undirected graph __G__ is a proper vertex coloring of __G__ (i.e., no two neighbors are assigned the same color) such that any path of length 3 in __G__ is not bicolored. The __star chromatic number__ of an undirected graph __G__, denoted by χ~s~(__G__), is the

Coloring with three-colored subgraphs
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

Interval coloring of (3,4)-biregular bip
Interval coloring of (3,4)-biregular bipartite graphs having large cubic subgraphs
✍ A. V. Pyatkin 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 80 KB

## Abstract An interval coloring of a graph is a proper edge coloring such that the set of used colors at every vertex is an interval of integers. Generally, it is an NP‐hard problem to decide whether a graph has an interval coloring or not. A bipartite graph __G__ = (__A__,__B__;__E__) is (α, β)‐b

Pancyclic subgraphs of random graphs
Pancyclic subgraphs of random graphs
✍ Choongbum Lee; Wojciech Samotij 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 249 KB

## Abstract An __n__‐vertex graph is called pancyclic if it contains a cycle of length __t__ for all 3≤__t__≤__n__. In this article, we study pancyclicity of random graphs in the context of resilience, and prove that if __p__>__n__^−1/2^, then the random graph __G__(__n, p__) a.a.s. satisfies the f