Color Class Sizes Of Triangle-Free Graphs

Keywords

Color critical vertices and graphs; Extremal graphs; Graph coloring; Triangle-free graphs

Abstract

For every graph G having chromatic number k there is a smallest positive integer i such that every k-coloring of G has at least i vertices in every color class and at least one kcoloring has exactly i vertices in at least one color class. The collection of all connected triangle-free graphs with given i and k is denoted G(i, k) and m(i, k) is the smallest order of a graph in G(i,k). This paper reviews the previously known values of m(i,k) and determines new values and bounds. Since any k-coloring of a graph in G(i, k) has at least i vertices in every color class, m(i, k) ≥ ik. It is shown that equality occurs for any k if i is sufficiently large.

Publication Date

2-1-2018

Publication Title

Journal of Combinatorial Mathematics and Combinatorial Computing

Volume

104

Number of Pages

231-244

Document Type

Article

Personal Identifier

scopus

Socpus ID

85045052513 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/85045052513

This document is currently not available here.

Share

COinS