Transitive orientations in bull-reducible Berge graphs |
| |
| Authors: | Celina de FigueiredoFrédéric Maffray Cláudia Villela Maciel |
| |
| Institution: | a Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brazilb C.N.R.S., Laboratoire G-SCOP, Grenoble, Francec Universidade Federal Fluminense, Niteroi, RJ, Brazil |
| |
| Abstract: | A bull is a graph with five vertices r,y,x,z,s and five edges ry, yx, yz, xz, zs. A graph G is bull-reducible if every vertex of G lies in at most one bull of G. We prove that every bull-reducible Berge graph G that contains no antihole is weakly chordal, or has a homogeneous set, or is transitively orientable. This yields a fast polynomial time algorithm to color the vertices of such a graph exactly. |
| |
| Keywords: | Perfect graph Coloring Comparability graph Bull-reducible graph |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
