Anzeige
Erschienen in:
2020 | OriginalPaper | Buchkapitel
Smallest \(C_{2l+1}\)-Critical Graphs of Odd-Girth \(2k+1\)
verfasst von : Laurent Beaudou, Florent Foucaud, Reza Naserasr
Erschienen in: Algorithms and Discrete Applied Mathematics
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Given a graph H, a graph G is called H-critical if G does not admit a homomorphism to H, but any proper subgraph of G does. Observe that \(K_{k-1}\)-critical graphs are the classic k-(colour)-critical graphs. This work is a first step towards extending questions of extremal nature from k-critical graphs to H-critical graphs. Besides complete graphs, the next classic case is odd cycles. Thus, given integers \(l\ge k\) we ask: what is the smallest order \(\eta (k,l)\) of a \(C_{2l+1}\)-critical graph of odd-girth at least \(2k+1\)? Denoting this value by \(\eta (k,l)\), we show that \(\eta (k,l)=4k\) for \(l\le k\le \frac{3l+i-3}{2}\) (\(2k=i\bmod 3\)) and that \(\eta (3,2)=15\). The latter is to say that a smallest graph of odd-girth 7 not admitting a homomorphism to the 5-cycle is of order 15 (there are at least 10 such graphs on 15 vertices).