The Matching Kneser Graph Conjecture For High Chromatic Numbers

MaRDI QIDQ6508859arXivFDO

Authors Saeed Shaebani

Published in arXiv

Abstract: oindent Alishahi and Hajiabolhassan found that for some classes of graphs, the wonderful equality ${\displaystyle }$chi left( G , rK_2 ight) = |E(G)| - { m ex} left( G , rK_2 ight)${\displaystyle }$ holds as an amazing relationship between chromatic number and generalized Tur'an number. This powerful equality enabled them to determine chromatic numbers of some interesting and important classes of graphs. They conjectured that the aforementioned equality holds for all connected graphs $G$. Iradmusa, by a nice elegant use of a class of cubic graphs, called snarks, made counterexamples to this conjecture for which $chileft(G,r{K}_{2}ight)=1$ and $|E(G)|-mexleft(G,r{K}_{2}ight)=3.$ In this paper, for any arbitrary positive integer $Theta$, we explicitly construct a sequence of trees $left(T_{r}ight{)}_{r=1}^{infty}$ for which ${\displaystyle }$lim_{r ightarrow infty} Bigl( |Eleft( T_r ight)| - { m ex} left( T_r , rK_2 ight) Bigr) = +infty${\displaystyle }$ while $chileft(T_r,r{K}_{2}ight)=Theta$ for all $rgeq3$.

This page was built for publication: The Matching Kneser Graph Conjecture For High Chromatic Numbers

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