On Indicated Chromatic Number of Graphs

详细信息    查看全文

• 作者：S. Francis Raj ; R. Pandiya Raj ; H. P. Patil
• 关键词：Indicated coloring ; Uniquely colorable graphs ; Color critical graphs ; Mycielski graphs
• 刊名：Graphs and Combinatorics
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：33
• 期：1
• 页码：203-219
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Combinatorics; Engineering Design;
• 出版者：Springer Japan
• ISSN：1435-5914
• 卷排序：33

文摘

Indicated coloring is a graph coloring game in which there are two players jointly coloring the vertices of a graph in such a way that both can see the entire graph at all the time and in each round the first player (Ann) selects a vertex, and then the second player (Ben) colors it properly without creating a monochromatic edge, using a fixed set of colors. The aim of Ann is to achieve a proper coloring for G, while Ben is trying to create a situation where all the colors occur on vertices adjacent to some uncolored vertex. The smallest number of colors necessary for Ann to win the game on a graph G (regardless of Ben’s strategy) is called the indicated chromatic number of G, and is denoted by \(\chi _i(G)\). In this paper, we obtain some upper bounds for the indicated chromatic number of graphs and find a smallest 3-regular graph for which the indicated chromatic number is 4. In addition, we introduce the concept of criticality of graphs with respect to the indicated chromatic number. Also we show that \(\{P_5,K_4-e\}\)-free graphs are k-indicated colorable for all \(k\ge \chi (G)\).