(δ, χ__{\sf FF})-bounded families of graphs

2016/05/13 by Manouchehr Zaker, Zaker, Manouchehr
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph theory and applications #Graph Labeling and Dimension Problems

paper · pdf · doi:10.48550/arxiv.1605.04267

Abstract

For any graph G, the First-Fit (or Grundy) chromatic number of G, denoted by χ__{\sf FF}(G), is defined as the maximum number of colors used by the First-Fit (greedy) coloring of the vertices of G. We call a family F of graphs (δ, χ__{\sf FF})-bounded if there exists a function f(x) with f(x)→ ∞ as x→ ∞ such that for any graph G from the family one has χ__{\sf FF}(G)≥ f(δ(G)), where δ(G) is the minimum degree of G. We first give some results concerning (δ, χ__{\sf FF})-bounded families and obtain a few such families. Then we prove that for any positive integer ℓ, Forb(K_ℓ,ℓ) is (δ, χ__{\sf FF})-bounded, where K_ℓ,ℓ is complete bipartite graph. We conjecture that if G is any C₄-free graph then χ__{\sf FF}(G)≥ δ(G)+1. We prove the validity of this conjecture for chordal graphs, complement of bipartite graphs and graphs with low minimum degree.

Related

• A note concerning the Grundy and \rm b-chromatic number of graphs
• The chromatic number of (P₅, K₅-e)-free graphs
• Induced subgraphs of graphs with large chromatic number. VII.\n Gy 'arf 'as' complementation conjecture
• On the chromatic number of some (P₃∪ P₂)-free graphs
• Chromatic bounds for some classes of 2K₂-free graphs