Upper bounds for the achromatic and coloring numbers of a graph

DOI10.1016/J.DAM.2016.09.005zbMATH Open1358.05120arXiv1511.00537OpenAlexW2962915229WikidataQ130351879 ScholiaQ130351879MaRDI QIDQ516843

Clive Elphick, Baoyindureng Wu

Publication date: 15 March 2017

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: Dvov{r}'ak emph{et al.} introduced a variant of the Randi'c index of a graph $G$, denoted by $R^{\prime }(G)$, where $R^{\prime }(G)=su{m}_{uvinE(G)}frac1maxd(u),d(v)$, and $d(u)$ denotes the degree of a vertex $u$ in $G$. The coloring number $col(G)$ of a graph $G$ is the smallest number $k$ for which there exists a linear ordering of the vertices of $G$ such that each vertex is preceded by fewer than $k$ of its neighbors. It is well-known that $chi(G)leqcol(G)$ for any graph $G$, where $chi(G)$ denotes the chromatic number of $G$. In this note, we show that for any graph $G$ without isolated vertices, $col(G)leq2R^{\prime }(G)$, with equality if and only if $G$ is obtained from identifying the center of a star with a vertex of a complete graph. This extends some known results. In addition, we present some new spectral bounds for the coloring and achromatic numbers of a graph.

Full work available at URL: https://arxiv.org/abs/1511.00537

zbMATH Keywords

chromatic number[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Randi%EF%BF%BD%EF%BF%BD+index&go=Go Randi�� index]achromatic numbercoloring number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Graph colorings with local constraints -- a survey
• Some eigenvalue properties in graphs (conjectures of Graffiti -- II)
• 25 pretty graph colouring problems
• Bounds of eigenvalues of graphs
• Conjectured bounds for the sum of squares of positive eigenvalues of a graph
• New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix
• Proof of a conjectured lower bound on the chromatic number of a graph
• Variable neighborhood search for extremal graphs. 23. On the Randić index and the chromatic number
• On the harmonic index and the chromatic number of a graph
• A proof for a conjecture on the Randić index of graphs with diameter
• A bound on the spectral radius of graphs with \(e\) edges
• On a relation between the Randić index and the chromatic number
• Sandwiching the (generalized) Randić index
• Randić index and the diameter of a graph
• On the conjecture of Aouchiche and Hansen about the Randić index
• Proof of the first part of the conjecture of Aouchiche and Hansen about the Randić index
• Randić index and coloring number of a graph

Cited In (12)

• Adjacency eigenvalues of graphs without short odd cycles
• Title not available (Why is that?)
• A Brualdi-Hoffman-Turán problem on cycles
• Two conjectured strengthenings of Turán's theorem
• Notes on the harmonic index of graphs
• Positive and negative square energies of graphs
• Nordhaus-Gaddum and other bounds for the sum of squares of the positive eigenvalues of a graph
• On the geometric-arithmetic index of a graph
• Upper bound for DP-chromatic number of a graph
• Upper bound in the Erdős-Hajnal problem of hypergraph coloring
• Generalising the achromatic number to Zaslavsky's colourings of signed graphs
• The harmonic index of a graph and its DP-chromatic number

Uses Software

• GRAFFITI

This page was built for publication: Upper bounds for the achromatic and coloring numbers of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q516843)