Paper Info
Title
Extremal Colorings and Independent Sets.
Abstract
We consider several extremal problems of maximizing the number of colorings and independent sets in some graph families with fixed chromatic number and order. First, we address the problem of maximizing the number of colorings in the family of connected graphs with chromatic number k and order n where \(k\ge 4\). It was conjectured that extremal graphs are those which have clique number k and size \({k\atopwithdelims ()2}+n-k\). We affirm this conjecture for 4-chromatic claw-free graphs and for all k-chromatic line graphs with \(k\ge 4\). We also reduce this extremal problem to a finite family of graphs when restricted to claw-free graphs. Secondly, we determine the maximum number of independent sets of each size in the family of n-vertex k-chromatic graphs (respectively connected n-vertex k-chromatic graphs and n-vertex k-chromatic graphs with c components). We show that the unique extremal graph is \(K_k\cup E_{n-k}\), \(K_1\vee (K_{k-1}\cup E_{n-k})\) and \((K_1 \vee (K_{k-1} \cup E_{n-k-c+1}))\cup E_{c-1}\) respectively.
Year
DOI
Venue
2018
10.1007/s00373-018-1951-3
Graphs and Combinatorics
Keywords
Field
DocType
Extremal graph, Coloring, Independent set, Chromatic number
Graph,Clique number,Combinatorics,Line graph,Independent set,Conjecture,Mathematics
Journal
Volume
Issue
ISSN
34
6
0911-0119
Citations 
PageRank 
References 
0
0.34
13
Authors
2
Name
Order
Citations
PageRank
John Engbers1216.79
Aysel Erey2194.99