首页 | 本学科首页   官方微博 | 高级检索  
     


On minimally b-imperfect graphs
Authors:Chí  nh T. Ho  ng, Cl  udia Linhares Sales,Fr  d  ric Maffray
Affiliation:aDepartment of Physics and Computer Science, Wilfrid Laurier University, 75 University Avenue West, Waterloo, Ontario, Canada N2L 3C5;bDepartamento de Computação, Universidade Federal do Ceará, Campus do Pici, Fortaleza, CE, Brazil;cC.N.R.S, Laboratoire G-SCOP, 46 Avenue Félix Viallet, 38031 Grenoble Cedex, France
Abstract:A b-coloring is a coloring of the vertices of a graph such that each color class contains a vertex that has a neighbour in all other color classes. The b-chromatic number of a graph G is the largest integer k such that G admits a b-coloring with k colors. A graph is b-perfect if the b-chromatic number is equal to the chromatic number for every induced subgraph H of G. A graph is minimally b-imperfect if it is not b-perfect and every proper induced subgraph is b-perfect. We give a list View the MathML source of minimally b-imperfect graphs, conjecture that a graph is b-perfect if and only if it does not contain a graph from this list as an induced subgraph, and prove this conjecture for diamond-free graphs, and graphs with chromatic number at most three.
Keywords:Coloration   b-coloring   a-chromatic number   b-chromatic number
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号