Title of article :
The t-improper chromatic number of random graphs
Author/Authors :
Kang، نويسنده , , Ross J. and McDiarmid، نويسنده , , Colin J.H Morton، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2007
Pages :
7
From page :
411
To page :
417
Abstract :
For a non-hamiltonian claw-free graph G with order n and minimum degree δ we show the following. If δ = 4 , then G has a 2-factor with at most ( 5 n − 14 ) / 18 components, unless G belongs to a finite class of exceptional graphs. If δ ⩾ 5 , then G has a 2-factor with at most ( n − 3 ) / ( δ − 1 ) components. These bounds are sharp in the sense that we can replace nor 5/18 by a smaller quotient nor δ − 1 by δ.
Keywords :
improper colouring , random graphs , graph colouring
Journal title :
Electronic Notes in Discrete Mathematics
Serial Year :
2007
Journal title :
Electronic Notes in Discrete Mathematics
Record number :
1454754
Link To Document :
بازگشت