- Tytuł:
- On 3-Colorings of Direct Products of Graphs
- Autorzy:
- Špacapan, Simon
- Powiązania:
- https://bibliotekanauki.pl/articles/31343446.pdf
- Data publikacji:
- 2019-05-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
independence number
direct product
Hedetniemi’s conjecture - Opis:
- The k-independence number of a graph G, denoted as αk(G), is the order of a largest induced k-colorable subgraph of G. In [S. Špacapan, The k-independence number of direct products of graphs, European J. Combin. 32 (2011) 1377–1383] the author conjectured that the direct product G × H of graphs G and H obeys the following bound αk(G×H)≤αk(G)|V(H)|+αk(H)|V(G)|−αk(G)αk(H), and proved the conjecture for k = 1 and k = 2. If true for k = 3 the conjecture strenghtens the result of El-Zahar and Sauer who proved that any direct product of 4-chromatic graphs is 4-chromatic [M. El-Zahar and N. Sauer, The chromatic number of the product of two 4-chromatic graphs is 4, Combinatorica 5 (1985) 121–126]. In this paper we prove that the above bound is true for k = 3 provided that G and H are graphs that have complete tripartite subgraphs of orders α3(G) and α3(H), respectively.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2019, 39, 2; 391-413
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł