On the b-coloring of P₄-tidy graphs

详细信息    查看全文

• 作者：Clara Iné ; s Betancur Velasquez ; Flavia Bonomo ; Ivo Koch
• 关键词： ; none ; color ; black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6TYW-51B8G2T-2&_mathId=mml29&_user=10&_cdi=5629&_pii=S0166218X10003446&_rdoc=8&_issn=0166218X&_acct=C000050221&_version=1&_userid=10&md5=ea9
• 刊名：Discrete Applied Mathematics
• 出版年：2011
• 出版时间：6 January 2011
• 年：2011
• 卷：159
• 期：1
• 页码：60-68
• 全文大小：263 K

文摘

A b-coloring of a graph is a coloring such that every color class admits a vertex adjacent to at least one vertex receiving each of the colors not assigned to it. The b-chromatic number of a graph G, denoted by χ_b(G), is the maximum number t such that G admits a b-coloring with t colors. A graph G is b-continuous if it admits a b-coloring with t colors, for every t=χ(G),…,χ_b(G), and it is b-monotonic if χ_b(H₁)≥χ_b(H₂) for every induced subgraph H₁ of G, and every induced subgraph H₂ of H₁. In this work, we prove that P₄-tidy graphs (a generalization of many classes of graphs with few induced P₄s) are b-continuous and b-monotonic. Furthermore, we describe a polynomial time algorithm to compute theb-chromatic number for this class of graphs.