Anzeige
Erschienen in:
2020 | OriginalPaper | Buchkapitel
Indicated Coloring of Complete Expansion and Lexicographic Product of Graphs
verfasst von : P. Francis, S. Francis Raj, M. Gokulnath
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
Indicated coloring is a slight variant of the game coloring which was introduced by Grzesik [6]. In this paper, we show that for any graphs G and H, G[H] is k-indicated colorable for all \(k\ge \mathrm {col}(G)\mathrm {col}(H)\). Also, we show that for any graph G and for some classes of graphs H with \(\chi (H)=\chi _i(H)=\ell \), G[H] is k-indicated colorable if and only if \(G[K_\ell ]\) is k-indicated colorable. As a consequence of this result we show that if \(G\in \mathcal {G}=\Big \{\)Chordal graphs, Cographs, \(\{P_5,C_4\}\)-free graphs, Complete multipartite graphs\(\Big \}\) and \(H\in \mathcal {F}=\Big \{\)Bipartite graphs, Chordal graphs, Cographs, \(\{P_5,K_3\}\)-free graphs, \(\{P_5,Paw\}\)-free graphs, Complement of bipartite graphs, \(\{P_5,K_4,Kite,Bull\}\)-free graphs, connected \(\{P_6,C_5,\overline{P_5},K_{1,3}\}\)-free graphs which contain an induced \(C_6\), \(\mathbb {K}[C_5](m_1, m_2 ,\ldots ,m_5)\), \(\{P_5,C_4\}\)-free graphs, connected \(\{P_5,\overline{P_2\cup P_3},\overline{P_5},\) \(Dart\}\)-free graphs which contain an induced \(C_5\Big \}\), then G[H] is k-indicated colorable for every \(k\ge \chi (G[H])\). This serves as a partial answer to one of the questions raised by Grzesik in [6].