On the b-Coloring of Cographs and P4-Sparse Graphs

被引:0
作者
Flavia Bonomo
Guillermo Durán
Frederic Maffray
Javier Marenco
Mario Valencia-Pabon
机构
[1] Universidad de Buenos Aires,CONICET and Departamento de Computación, FCEN
[2] Universidad de Buenos Aires,CONICET and Departamento de Matemática, FCEN
[3] U. de Chile,Departamento de Ingeniería Industrial, FCFM
[4] C.N.R.S.,Instituto de Ciencias
[5] Laboratoire G-SCOP,undefined
[6] Universidad Nacional de General Sarmiento,undefined
[7] LIPN,undefined
[8] Université Paris-Nord,undefined
来源
Graphs and Combinatorics | 2009年 / 25卷
关键词
b-coloring; b-continuity; b-monotonicity; cographs; -sparse graphs;
D O I
暂无
中图分类号
学科分类号
摘要
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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$t = \chi(G), \ldots, \chi_b(G)$$\end{document} . We define a graph G to be b-monotonic if χb(H1) ≥ χb(H2) for every induced subgraph H1 of G, and every induced subgraph H2 of H1. In this work, we prove that P4-sparse graphs (and, in particular, cographs) are b-continuous and b-monotonic. Besides, we describe a dynamic programming algorithm to compute the b-chromatic number in polynomial time within these graph classes.
引用
收藏
页码:153 / 167
页数:14
相关论文
共 25 条
[11]  
Kouider M.(2002)On the b-chromatic number of a graph Lect. Notes Comput. Sci 2573 310-320
[12]  
Irving R.W.(undefined)undefined undefined undefined undefined-undefined
[13]  
Manlove D.F.(undefined)undefined undefined undefined undefined-undefined
[14]  
Jamison B.(undefined)undefined undefined undefined undefined-undefined
[15]  
Olariu S.(undefined)undefined undefined undefined undefined-undefined
[16]  
Jamison B.(undefined)undefined undefined undefined undefined-undefined
[17]  
Olariu S.(undefined)undefined undefined undefined undefined-undefined
[18]  
Jansen K.(undefined)undefined undefined undefined undefined-undefined
[19]  
Scheffler P.(undefined)undefined undefined undefined undefined-undefined
[20]  
Woeginger G.J.(undefined)undefined undefined undefined undefined-undefined