Some relations among term rank, clique number and list chromatic number of a graph
type: Item
instance of: scholarly article
title: Some relations among term rank, clique number and list chromatic number of a graph
zbMATH Open document ID: 1111.05031
author: Hamid-Reza Fanaï
author: S. Akbari
published in: Discrete Mathematics
publication date: 2006-12-14T00:00:00Z
review text: By \(G\) we mean the graphs which are nonempty, finite, undirected, with no loops, parallel edges or isolated vertex. The following is proved: For any graph \(G,\chi(G)\leq (R(G)+ \omega(G))/2\), where \(\chi(G)\), \(R(G)\), \(\omega(G)\) are the list chromatic number, term rank, size of the maximum clique of \(G\), respectively. If \(\omega(G)\neq 2\), equality holds if and only if \(G\) is the complete graph \(K_n\). Moreover, if equality holds and \(\omega(G)= 2\), then \(G\) is a bipartite graph. Some consequences are considered, too.
reviewed by: Jozef Fiamčík
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 5080052
zbMATH Keywords: \(k\)-choosable
MaRDI profile type: Publication
full work available at URL: j.disc.2004.11.028
OpenAlex ID: W1992773164
cites work: A counterexample to the rank-coloring conjecture
cites work: Q3922703
cites work: Rank, term rank, and chromatic number
cites work: Q4304370
cites work: Rank and chromatic number of a graph
cites work: The rank and size of graphs
cites work: Q4382863
cites work: A Bound for the Chromatic Number of a Graph
cites work: Q4135588
DOI: 10.1016/J.DISC.2004.11.028
Recommended article: Rank, term rank and chromatic number of a graph
Recommended article: Rank, term rank, and chromatic number
Recommended article: Some relations between rank, chromatic number and energy of graphs
Recommended article: The list chromatic number of graphs with small clique number
Recommended article: On Cliques and Clique Chromatic Numbers in Line, Lict and Lictact Graphs
Recommended article: On the graph chromatic number and the rank of a matrix associated with the graph
Recommended article: Rank and chromatic number of a graph
Recommended article: On the connection between chromatic number, maximal clique and minimal degree of a graph
Recommended article: THE CLIQUE NUMBERS AND CHROMATIC NUMBERS OF CERTAIN PALEY GRAPHS
Recommended article: Chromatic number versus chromatic number in graphs with bounded clique number
description: scientific article; zbMATH DE number 5080052