Homomorphisms from sparse graphs to the Petersen graph
2010; Elsevier BV; Volume: 310; Issue: 20 Linguagem: Inglês
10.1016/j.disc.2010.04.002
ISSN1872-681X
Autores Tópico(s)Nuclear Receptors and Signaling
ResumoLet G be a graph and let c: V(G)→({1,…,5}2)be an assignment of 2-elements subsets of the set {1,…,5} to the vertices of G such that for any two adjacent vertices u and v,c(u) and c(v) are disjoint. Call such a coloring c a (5, 2)-coloring of G. A graph is (5,2)-colorable if and only if it has a homomorphism to the Petersen graph. The maximum average degree of G is defined as Mad(G)=max{2|E(H)||V(H)|:H⊆G}. In this paper, we prove that every triangle-free graph with Mad(G)<52 is homomorphic to the Petersen graph. In other words, such a graph is (5, 2)-colorable. Moreover, we show that the bound on the maximum average degree in our result is best possible.
Referência(s)