On a problem concerning ordered colourings |
| |
Authors: | Louis Caccetta Rui Zhong Jia |
| |
Institution: | School of Mathematics and Statistics, Curtin University of Technology, GPO Box U1987, Perth, Western Australia, 6845, Australia |
| |
Abstract: | Let G be a connected graph with v(G) 2 vertices and independence number (G). G is critical if for any edge e of G: 1. (i) (G − e) > (G), if e is not a cut edge of G, and 2. (ii) v(Gi) − (Gi) < v(G) − (G), I = 1, 2, if e is a cut edge and G1, G2 are the two components of G − e.
Recently, Katchalski et al. (1995) conjectured that: if G is a connected critical graph, then
with equality possible if and only if G is a tree. In this paper we establish this conjecture. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|